世界的尽头

以下公式均采用从 $1$ 开始的下标，并约定所有下标为 $0$ 的位置值为 $0$ 。

一维前缀和

对于原数组 $a$ ，定义前缀和数组 $S$ ：

S_i = \sum_{k=1}^{i} a_k, \qquad S_0 = 0

递推公式为：

S_i = S_{i-1} + a_i

区间 $[L,R]$ 的元素和为：

\sum_{i=L}^{R} a_i = S_R - S_{L-1}

for (int i = 1; i <= n; i++) {
  S[i] = S[i - 1] + a[i];
}
 
// [L, R] 的区间和
int sum = S[R] - S[L - 1];

二维前缀和

对于矩阵 $a$ ，定义 $S_{i,j}$ 为左上角 $(1,1)$ 到右下角 $(i,j)$ 的矩形区域之和：

S_{i,j} = \sum_{x=1}^{i}\sum_{y=1}^{j} a_{x,y}

根据容斥原理，递推公式为：

S_{i,j} = S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1} + a_{i,j}

以 $(x_1,y_1)$ 为左上角、 $(x_2,y_2)$ 为右下角的子矩阵元素和为：

\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2} a_{i,j} = S_{x_2,y_2} - S_{x_1-1,y_2} - S_{x_2,y_1-1} + S_{x_1-1,y_1-1}

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];
  }
}
 
// (x1, y1) 到 (x2, y2) 的子矩阵和
int sum = S[x2][y2] - S[x1 - 1][y2]
        - S[x2][y1 - 1] + S[x1 - 1][y1 - 1];

一维差分

差分是前缀和的逆运算。对于原数组 $a$ ，定义差分数组 $b$ ：

b_i = a_i - a_{i-1}, \qquad a_0 = 0

对差分数组求前缀和即可还原原数组：

a_i = \sum_{k=1}^{i} b_k = a_{i-1} + b_i

如果要给区间 $[L,R]$ 中的每个元素都加上 $c$ ，只需修改两个边界：

\begin{aligned} b_L &\mathrel{+}= c, \\ b_{R+1} &\mathrel{-}= c \end{aligned}

// 构造差分数组
for (int i = 1; i <= n; i++) {
  b[i] = a[i] - a[i - 1];
}
 
// 给 [L, R] 中的每个元素加 c
b[L] += c;
b[R + 1] -= c;
 
// 还原修改后的数组
for (int i = 1; i <= n; i++) {
  a[i] = a[i - 1] + b[i];
}

797 差分

#include <iostream>
using namespace std;
 
const int N = 100010;
 
int a[N],b[N];
 
int n,m;
 
void insert(int l,int r,int c) {
    b[l] += c;
    b[r+1] -= c;
}
 
int main() {
    scanf("%d%d",&n,&m);
    
    for (int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
        insert(i,i,a[i]);
    }
 
    while(m--) {
        int l ,r ,c;
        scanf("%d%d%d",&l,&r,&c);
        insert(l,r,c);
    }
 
    for (int i = 1;i <= n;i++) {
        b[i] += b[i-1];
        printf("%d ",b[i]);
    }
    return 0;
}

二维差分矩阵

二维差分同样是二维前缀和的逆运算。定义差分矩阵 $b$ ：

b_{i,j} = a_{i,j} - a_{i-1,j} - a_{i,j-1} + a_{i-1,j-1}

对 $b$ 求二维前缀和即可还原 $a$ ：

a_{i,j} = a_{i-1,j} + a_{i,j-1} - a_{i-1,j-1} + b_{i,j}

如果要给以 $(x_1,y_1)$ 为左上角、 $(x_2,y_2)$ 为右下角的子矩阵中每个元素都加上 $c$ ，则：

\begin{aligned} b_{x_1,y_1} &\mathrel{+}= c, \\ b_{x_1,y_2+1} &\mathrel{-}= c, \\ b_{x_2+1,y_1} &\mathrel{-}= c, \\ b_{x_2+1,y_2+1} &\mathrel{+}= c \end{aligned}

#include <iostream>
using namespace std;
 
const int N = 1010;
 
int b[N][N];
 
int a[N][N];
 
int n, m, q;
 
void insert(int x1, int y1, int x2, int y2, int c) {
  b[x1][y1] += c;
  b[x1][y2 + 1] -= c;
  b[x2 + 1][y1] -= c;
  b[x2 + 1][y2 + 1] += c;
}
 
int main() {
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      int x;
      cin >> x;
      a[i][j] = x;
      insert(i, j, i, j, x);
    }
  }
  int x1, x2, y1, y2, c;
  while (q--) {
    cin >> x1 >> y1 >> x2 >> y2 >> c;
    insert(x1, y1, x2, y2, c);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      printf("%d ", a[i][j]);
    }
    puts("");
  }
}

3-前缀和&差分

一维前缀和

二维前缀和

一维差分

二维差分矩阵