【基础算法】前缀和、二维前缀和

前缀和

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

C++代码：

#include 
using namespace std;

int N, A[10000], B[10000];
int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  // 前缀和数组的第一项和原数组的第一项是相等的。
  B[0] = A[0];

  for (int i = 1; i < N; i++) {
    // 前缀和数组的第 i 项 = 原数组的 0 到 i-1 项的和 + 原数组的第 i 项。
    B[i] = B[i - 1] + A[i];
  }

  for (int i = 0; i < N; i++) {
    cout << B[i] << " ";
  }

  return 0;
}

模板题：AcWing 795. 前缀和

#include 

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

int main()
{
    scanf("%d%d", &n, &m);
    
    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];//前缀和的初始化
    
    while(m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);//区间和计算
    }
    return 0;
}

二维前缀和

这里的子矩阵是以\((x_1,y_1)\)为左上角，\((x_2, y_2)\)右下角的子矩阵。

注意，这里公式很容易记错，看下这个图就明白了。

例题：P1387 最大正方形

#include 
#include 
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 = 1;

  int l = 2;
  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;
}

模板题：AcWing 796. 子矩阵的和

#include 

using namespace std;

const int N = 1010;

int a[N][N], s[N][N];

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", &a[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[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
        
    }
    return 0;
}

参考：https://oi-wiki.org/basic/prefix-sum/#fn:note1