前缀和

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为：数列的前n项的和

一维前缀和

B[i] = B[i-1] + A[i]

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 10010;
  4. int a[N],b[N],n;
  6. int main()
  7. {
  8.     cin >> n;
  9.     for (int i = 1;i <= n;i ++) {
  10.         cin >> a[i];
  11.     }
  12.     for (int i = 1;i <= n;i ++) {
  13.         // 前缀和数组的第i项 = 原数组的 0 到 i-1 项的和 + 原数组的第 i 项
  14.         b[i] = b[i-1] + a[i];
  15.     }
  16.     for (int i = 1;i <= n;i ++) {
  17.         cout << b[i] << " ";
  18.     }
  19.     return 0;
  20. }

二维前缀和

基于容斥原理
S[i,j] = S[i-1,j] + S[i,j-1] - S[i-1,j-1] + A[i,j]

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 10010;
  4. int a[N][N],b[N][N],n,m;
  6. int main()
  7. {
  8.     cin >> n >> m;
  9.     for (int i = 1;i <= n;i ++) {
  10.         for (int j = 1;j <= m;j ++) {
  11.             cin >> a[i][j];
  12.         }
  13.     }
  14.     for (int i = 1;i <= n;i ++) {
  15.         for (int j = 1;j <= m;j ++) {
  16.             b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j];
  17.         }
  18.     }
  19.     for(int i = 1;i <= n;i ++ ) {
  20.         for(int j = 1;j <= m;j++ ) {
  21.             cout << b[i][j] << " ";
  22.         }
  23.         cout << endl;
  24.     }
  25.     return 0;
  26. }

(x1,y1) - (x2,y2) = S[x2,y2] - S[x1-1,y2] - S[x2,y1-1] + S[x1-1,y1-1]

差分

差分是一种和前缀和相对的策略，可以当做是求和的逆运算
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c