基础算法——前缀和与差分

前缀和与差分

1.一维前缀和

1.1 前缀和的定义

$ s[n]=$一个数组中（下标从1开始）前n个数据的和

1.2 算法思想与模板

//数组中下标含0的元素始终为0，例如a[0] = 0, s[0] = 0
for (int i = 1; i <= n; i ++ ){
	cin >> a[i];
	s[i] = s[i - 1] + a[i];
}

以(o1)的时间复杂度得到某块区间的总和

2. 二维前缀和

2.1 算法思想与模板

利用容斥原理

//数组中下标含0的元素始终为0，例如a[0][0] = 0, s[0][0] = 0; a[0][1] = 0......
S[i, j] = 第i行j列格子左上部分所有元素的和
//以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

3. 一维差分

差分部分参考了CSDN上的文章，原文链接：

差分 --算法竞赛专题解析（32）_罗勇军的博客-CSDN博客

3.1 一维差分的定义

讨论这样一个场景：

1. 给定一个长度为n的一维数组a[]，数组内每个元素有初始值。

2. 修改操作：做m次区间修改，每次修改对区间内所有元素做相同的加减操作。例如第i次修改，把区间$[ L_i , R_i ] $(注意是闭区间)内所有元素加上$d_i $。

3. 询问操作：询问一个元素的新值是多少。

• 如果简单地用暴力法编码，那么每次修改的复杂度是O(n)的，m次修改共O(mn)，总复杂度O(mn)，效率很差。利用差分法，可以把复杂度减少到O(m+n)。

• 在差分法中，用到了两个数组：原数组a[]、差分数组D[]。
  差分数组D[ ]的定义是D[k] = a[k] − a[k − 1]，即原数组a[ ]的相邻元素的差，也可以假想成**a[n]是差分数组D[]的前n个元素的和**。

  • 从定义可以推出a[k] = D[1] + D[2] + . . . + D[k] ，也就是说，a[]是D[]的前缀和。这个公式揭示了a[]和D[]的关系，“差分是前缀和的逆运算”，它把求a[k]转化为求D的前缀和。
  • 注意，a[]和D[]的值都可能为负，下面图中所有的D[]都是长度为正的线段，只是为了方便图示。

理解：将a[]想象成线上的点，将D[]想象成点前的区间

3.2 算法思想

把区间[ L , R ]内每个元素加上d ，对应的D[ ] 做以下操作：

1. 把D [ L ] 加上d ：

 D[L] += d

2. 把D [ R + 1 ] 减去d ：

 D[R+1] -= d

每次操作只需要修改区间[L,R]的两个端点的D[]值，复杂度是O(1)的。经过这种操作后，原来直接在a[]上做的复杂度为O(n)的区间修改操作，就变成了在D[]上做的复杂度为O(1) 端点操作。

利用D[]，能精确地实现只修改区间内元素的目的，而不会修改区间外的a[]值。因为前缀和= D[1] + D[2] + . . . + D[x]，有：
1）1 ≤ x < L ，前缀和a[x]不变；
2）L ≤ x ≤ R ，前缀和a[x]增加了d ；
3）R < x ≤ N ，前缀和a[x]不变，因为被D[R+1]中减去的d抵消了。

完成区间修改并得到D[]后，最后用D[]计算a[]，复杂度是O(n)的。m次区间修改和1次查询，总复杂度为O(m+n)，比暴力法的O(mn)好多了。

3.3 算法模板

//数组中下标为1的元素始终为0,例如a[0] = 0, D[0] = 0;
//给区间[l, r]中的每个数加上c：
D[l] += c;
D[r + 1] -= c;

3.4 差分的局限性

​ 利用差分数组D[]可以把O(n)的区间修改，变成O(1)的端点修改，从而提高了修改操作的效率。
  但是，一次查询操作，即查询某个a[i]，需要用D[]计算整个原数组a[]，计算量是O(n)的，即一次查询的复杂度是O(n)的。在上面的例题中，如果查询不是发生了一次，而是这样：有m次修改，有k次查询，且修改和查询的顺序是随机的。此时总复杂度是：m次修改，复杂度O(m)，k次查询复杂度O(kn)，总复杂度O(m+kn)。还不如直接用暴力法，总复杂度O(mn+k)。
  这种题型是“区间修改+单点查询”，用差分数组往往不够用。因为差分数组对“区间修改”很高效，但是对“单点查询”并不高效。此时需要用树状数组和线段树来求解

4. 二维差分

4.1 算法思想

将a[][]想象成图上的每个点，将D[][]想象成点前的每一块，每一个点的大小等于从左上角到该点所能划出矩形的面积

只有

D[x1, y1] += c;
D[x2 + 1, y1] -= c;
D[x1, y2 + 1] -= c;
D[x2 + 1, y2 + 1] += c;

这样划分，才能仅影响蓝色区域中的九个点

4.2 算法模板

//数组中下标含0的元素始终为0,例如a[0][0] = 0, D[0][0] = 0; a[0][1] = 0......
//给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
D[x1, y1] += c;
D[x2 + 1, y1] -= c;
D[x1, y2 + 1] -= c;
D[x2 + 1, y2 + 1] += c;