数学 前缀和与差分

前缀和与差分

1.1 一维数组的前缀和

• 对数列 A [1,2,3,4,5] ,求数列B,使$B_i={\sum }_{k=0}^i{A}_k$

思路： 因为B[0] = A[0] 且有递推式 $B_i=B_{i-1}+A_i$构造递推式

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    vector<int> A = {1, 2, 3, 4, 5, 6};
    vector<int> B(A.size());
    B[0] = A[0];
    for (size_t i = 1; i < A.size(); i++) {
        B[i] = B[i - 1] + A[i];
    }
    for (auto &&i : B) cout << i << " ";
    //输出: 1 3 6 10 15 21
    return 0;
}

于传统代码相比，将时间复杂度从$O(n^2)$降低到$O(n)$且空间复杂度仍然是$O(n)$

1.2 二维数组的前缀和

对一个二维数组A:

$$A=\left[\begin{array}{cccc}1& 2& 3& 4\\ 5& 6& 7& 8\\ 9& 10& 11& 12\end{array}\right]$$

二维数组前缀和定义：存在二维数组S，有：

$$S_{i,j}=\sum _{k_1=0}^i\sum _{k_2=0}^j{A}_{k_1,k_2}$$

类比一维的情形，$S_{i,j}$应该可以基于$S_{i-1,j}$或 $S_{i,j-1}$ 计算，从而避免重复计算前面若干项的和。但是，如果直接将$S_{i-1,j}$和 $S_{i,j-1}$ 相加，再加上 $A_{i,j}$，会导致重复计算 $S_{i-1,j-1}$ 这一重叠部分的前缀和，所以还需要再将这部分减掉。这就是 容斥原理。由此得到如下递推关系：

$$S_{i,j}=A_{i,j}+S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}$$

简单代码实现:

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //在构建A的时候可以将A整体向右下移一个单位防止负数下标的出现
    vector<vector<int>> A = {
        {0, 0, 0, 0, 0},
        {0, 1, 2, 3, 4},
        {0, 5, 6, 7, 8},
        {0, 9, 10, 11, 12},
    };
    vector<vector<int>> S(A.size(), vector<int>(A[0].size()));
    S[1][1] = A[1][1];
    for (size_t i = 1; i < A.size(); i++) {
        for (size_t j = 1; j < A[0].size(); j++) {
            if (i == j && i == 1) continue;
            S[i][j] = A[i][j] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
        }
    }
    for (auto &&i : S) {
        for (auto &&j : i) {
            cout << j << " ";
        }
        cout << endl;
    }
    /*输出：
    0 0 0 0 0
    0 1 3 6 10
    0 6 14 24 36
    0 15 33 54 78
    */
    return 0;
}

例：洛谷 P1387 最大正方形

最大正方形

题目描述

在一个 $n\times m$ 的只包含 $0$ 和 $1$ 的矩阵里找出一个不包含 $0$ 的最大正方形，输出边长。

输入格式

输入文件第一行为两个整数 $n,m(1\le n,m\le 100)$，接下来 $n$ 行，每行 $m$ 个数字，用空格隔开，$0$ 或 $1$。

输出格式

一个整数，最大正方形的边长。

样例 #1

样例输入 #1

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

样例输出 #1

2

解决思路：

1. 先使用二维前缀和数组将输入数组$A$的$A_{1,1}\to A_{i,j}$的和表示出来

2. 设立边长$l$从1开始找最小正方形，其过程如下：

   1. 设立$i,j$作为假设正方形的右下角点,找的正方形为以$l$为边长，底点为$(i,j)$的一个正方形

   2. 显然$i,j$均从$l$开始，到m,n结束

   3. b[i][j] - b[i - l][j] - b[i][j - l] + b[i - l][j - l] == l * l作为判断标准(why)

• b[i][j]是从$(1,1)\to (i,j)$的前项和，我们需要求 $(i-l,j-l)\to (i,j)$ 的和

  ![[Pasted image 20250123215240.png]]
  ![[Pasted image 20250123215327.png]]
  

• 不难发现：我们想求的是黄色部分的前缀和并判断其是否等于$l^2$

• 我们可以发现求黄色部分就是将$b(i,j)$减去图一蓝色的部分，可以减去两矩形的面积$b(i-l,j),b(i,j-l)$,但显然会多减去图二绿色部分的区域，所以我们需要利用容斥定理加上$b(i-l,j-l)$的面积

• 所以我们便得到了黄色部分的递推表达式:

  $$locans=b_{i,j}-b_{i-l,j}-b_{i,j-l}+b_{i-l，j-l}$$

• 现在判断$locans$与$l^2$的关系即可
• 完成一次查找之后就可以让 $l$ 增加,显然 $l\in [1,\min (n,m)]$
  示例代码：

#include <algorithm>
#include <iostream>
using namespace std;
int a[103][103];
int b[103][103];  // 前缀和数组，相当于上文的 sum[]
 
int main() {
  int n, m;
  cin >> n >> m;
 
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      b[i][j] =
          b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + a[i][j];  // 求前缀和
    }
  }
 
  int ans = 0;
 
  int l = 1;
  while (l <= min(n, m)) {  // 判断条件
    for (int i = l; i <= n; i++) {
      for (int j = l; j <= m; j++) {
        if (b[i][j] - b[i - l][j] - b[i][j - l] + b[i - l][j - l] == l * l) {
          ans = max(ans, l);  // 在这里统计答案
        }
      }
    }
    l++;
  }
 
  cout << ans << endl;
  return 0;
}

Tip

上面进行的操作便是在前缀和中寻找某一区域的和的操作，利用这个思想，我们可以寻找任意大小的区域和，可以从容斥定理入手，进行区域和的计算

树上前缀和

• 一维数组树上前缀和
  1. 在求解一维数组之前我们要进行一次前缀和操作
  2. 对数组$A$的$[l,r]$区间，其区间和如下：

$$sum[l,r]=S[r]-S[l-1]$$

时间复杂度：构造前缀和数组$O(n)$,查询区间和$O(1)$

• 二维数组树上前缀和
  1. 与一维数组树上前缀和一样，二维树上前缀和也需要提前做好前缀和工作
  2. 快速求任意子矩阵的和

$$\text{sum}([x_1,y_1],[x_2,y_2])=S[x_2][y_2]-S[x_1-1][y_2]-S[x_2][y_1-1]+S[x_1-1][y_1-1]$$

其中：

• $S[x_1][y_2]$：从 [1,1]到[$x_1,y_1$]的矩形和；
• $S[x_2][y_2]$：从 $[1,1]$ 到 $[x_2,y_2]$ 的矩形和；
• $-S[x_1-1][y_2]$：减去上方多余的矩形；
• $-S[x2][y1-1]$: 减去左侧多余的矩形；
• $+S[x1-1][y1-1]$：加回左上角重复减去的部分。

Tip

要注意的是在减去左边和上边的矩形的时候，下标都为$S[x_1-1][y_2]$和 $S[x_2][y_1-1]$

差分

• 指找数组范围内某一两项的差

• 定义：$diff[i]=a_i-a_{i-1}$ 特别的：$i=1$时，$diff[1]=a_1$

• 差分和原数组的关系 性质：

  • 我们将差分数组做一次前项和得到的即为原数组
  • 显然：我们对前缀和数组做一次差分得到的就是原数组
    差分计算数组动态变化

• 对数组$A$的$[l,r]$区间同时加$k$有：

	diff[l] += k
	diff[r+1] -= k

此时再进行一次前缀和，即可完成原始数组的复原

for(int i = 1; i <= diff.size() ; i++){
    sum[i] = sum[i-1] + d[i];
}