【基礎算法】字首和、二維字首和

字首和

字首和是一種重要的預處理，能大大降低查詢的時間複雜度。可以簡單了解為“數列的前\(n\)項的和”。

C++代碼：

#include <iostream>
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 <iostream>

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)\)右下角的子矩陣。

注意，這裡公式很容易記錯，看下這個圖就明白了。

#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 = 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;
}
           

#include <iostream>

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;
}