【算法基础】基础算法（二）--（高精度、前缀和、差分）（上）https://developer.aliyun.com/article/1514661?spm=a2c6h.13148508.setting.29.4b904f0ejdbHoA
2、注意事项
a. 长度不一致
首先进行比较判断，如果 A < B，则将 0 添加到结果 C 中，得商为 0，并将余数 r 赋值为 A，得 r == A，然后返回结果 C。
b. k 的作用
用于记录每次除法计算中的商。
c. 去除前导 0
这段代码有两处去除前导 0 的地方，其中一处含义与之前一致，另外一处是：如果余数 r 的长度 > 1 且末尾元素为 0，则将末尾的 0 删除，保持余数的最小表示形式，这段代码的目的是去除余数前导的零。
d. 代码解释
vector<int> div(vector<int> &A, vector<int> &B, vector<int> &r) { vector<int> C; if (!cmp(A, B)) { C.push_back(0); r.assign(A.begin(), A.end());//使得r和A的内容一致 return C; } int j = B.size(); r.assign(A.end() - j, A.end());//将A的末尾与除数B长度相同的部分赋值给变量r while (j <= A.size()) { //循环执行除法运算 直到处理完所有的被除数 int k = 0;//记录每次除法计算中的商 while (cmp(r, B)) {//直到余数r小于除数B为止 r = sub(r, B);//将r减去除数B得到新的余数r k ++;//每执行一次减法运算，商的个数k就+1 } C.push_back(k);//将每次除法计算得到的商k添加到C的末尾 用于存储所有的商 if (j < A.size()) r.insert(r.begin(), A[A.size() - j - 1]);//将下一个被除数数字添加到余数r if (r.size() > 1 && r.back() == 0) r.pop_back();//去除余数前导的零 j++; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; }
（3）练习
二、前缀和与差分
1、前缀和
前缀和可以用于快速计算一个序列的区间和，也有很多问题里不是直接用前缀和，但是借用了前缀和的思想。
（1）一维前缀和
预处理出一个前缀和数组后，要求一段区间和可以使用O(1)的时间复杂度快速求出。
【公式】
预处理 ： s [ i ] = a [ i ] + a [ i - 1 ]
求区间 [ l ， r ]： sum = s [ r ] - s [ l - 1 ]
" 前缀和数组 " 和 " 原数组 " 可以合二为一
给定一个 a 数组，请求出它的前缀和数组 s ：
那么 a 数组的前缀和数组为：
a 数组与 s 数组之间满足：s[i] = a[0] + a[1] + a[2] + … + a[i]
由于我们在计算前缀和时，为了更加方便，我们会将数组下标从 1 开始存入和读取。
所以，我们的 s 前缀和数组为： s[i] = a[1] + a[2] + … + a[i]
如果要求某个区间的和该怎么办？
用以上的例子，我们想求 a 数组中下标从 3 到 6 的数值的和。如下图：
用前缀和原理分析可知：a[3] + a[4] + a[5] + a[6] = s[6] - s[2]
【一维前缀和模板】
🔺记忆！
const int N=100010; int a[N]; int main(){ int n,m; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)a[i]=a[i-1]+a[i]; scanf("%d",&m); while(m--){ int l,r; scanf("%d%d",&l,&r); printf("%d\n",a[r]-a[l-1]); } return 0; }
写法二：
const int N=100010; int a[N], s[N]; int main(){ int n,m; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i]; scanf("%d",&m); while(m--){ int l,r; scanf("%d%d",&l,&r); printf("%d\n",s[r]-s[l-1]); } return 0; }
【练习】
（2）二维前缀和
计算矩阵的前缀和： s [ x ][ y ] = s [ x - 1 ][ y ] + s [ x ][ y - 1 ] - s [ x - 1 ][ y - 1 ] + a [ x ][ y ]
以 ( x1 ， y1 ) 为左上角， ( x2 ， y2 ) 为右下角的子矩阵的和为：
计算子矩阵的和： s = s [ x2 ][ y2 ] - s [ x1 - 1 ][ y2 ] - s [ x2 ][ y1 - 1 ] + s [ x1 - 1 ][ y1 - 1 ]
思路二：
假如我们要求 s[2][3] ，可以根据画图来理解。
s[2][3] 实际上等于下图中绿色区域中数值的和。
我们又可以将这绿色区域划分成以下几种。
我们可以用表达式表示成：s[2][3] = s[2][2] + s[1][3] - s[1][2] + a[2][3]
因为我们在求 s[2][2] 和 s[1][3] 时会求和两次 s[1][2]， 所以我们需要再减去一次 s[1][2]。
【二维前缀和模板】
🔺记忆！
int s[1010][1010]; int n,m,q; int main(){ scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&s[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; while(q--){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]); } return 0; }
写法二：
int a[1010][1010], s[1010][1010]; int n,m,q; int main(){ scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&s[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]; while(q--){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]); } return 0; }
【练习】
2、差分
差分是前缀和的逆运算，对于一个数组 a ，其差分数组 b 的每一项都是 a[i] 和前一项 a[i−1] 的差。
注意：差分数组和原数组必须分开存放！
- 定义：对于已知有 n 个元素的离线数列 a，我们可以建立记录它每项与前一项差值的差分数组 b：显然，b[1] = a[1] - 0 = a[1]; 对于整数 i ∈ [2，n]，我们让 b[i] = a[i] - a[i-1]。
- 简单性质：（1）计算数列各项的值：观察 a[2] = b[1]+b[2] = a[1] + (a[2] - a[1]) = a[2] 可知，数列第 i 项的值是可以用差分数组的前 i 项的和计算的，即 a[i] = b[i] 的前缀和。
（1）一维差分
给区间 [ l ， r ] 中的每个数加上 c ：b [ l ] += c ，b [ r + 1 ] -= c
【一维差分和模板】
🔺记忆！
using namespace std; int a[100010],s[100010]; int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)s[i]=a[i]-a[i-1];// 读入并计算差分数组 while(m--){ int l,r,c; cin>>l>>r>>c; s[l]+=c; s[r+1]-=c;// 在原数组中将区间[l, r]加上c } for(int i=1;i<=n;i++){ s[i]+=s[i-1]; cout<<s[i]<<' '; }// 给差分数组计算前缀和，就求出了原数组 return 0; }
（2）二维差分
给以 ( x1 ， y1 ) 为左上角， ( x2 ， y2 ) 为右下角的子矩阵中的所有元素加上 c ：
b[x1，y1] += c，b[x2+1，y1] -= c，b[x1，y2+1] -= c，b[x2+1，y2+1] += c
二维差分用于在一个矩阵里，快速里把矩阵的一个子矩阵加上一个固定的数。也是直接来修改差分矩阵。试想只要在差分矩阵的(x1，y1) 位置加上 c，那么以它为左上角，所有后面的元素就都加上了 c。要让(x2，y2) 的右边和下边的元素不受影响，由容斥原理可以知道，只要在(x2+1，y1) 和(x1，y2+1) 位置减去 c，再从(x2+1，y2+1) 位置加回 c 就可以了。
【二维差分模板】
🔺记忆！
const int N = 1e3 + 10; int a[N][N], b[N][N]; void insert(int x1, int y1, int x2, int y2, int c) { b[x1][y1] += c; b[x2 + 1][y1] -= c; b[x1][y2 + 1] -= c; b[x2 + 1][y2 + 1] += c; } int main() { int n, m, q; cin >> n >> m >> q; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { insert(i, j, i, j, a[i][j]); //构建差分数组 } } while (q--) { int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; insert(x1, y1, x2, y2, c);//加c } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; //二维前缀和 } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { printf("%d ", b[i][j]); } printf("\n"); } return 0; }
⚪注意事项
为什么构建差分数组时，是插入i，j，i，j？
使用相同的坐标来作为左上角和右下角的坐标是没有问题的，因为这样可以确保只插入一个元素。
