前缀和

前缀和可以用O(1)的时间解决某区间的求和问题。
求前缀和的时间复杂度为O(n)。

一维前缀和

  1. for (int i = 1; i <= n; i ++) {
  2.     cin >> s[i];
  3.     // 求解前缀和，s[i]表示从(1-i)的元素的和
  4.     // 下标从1开始
  5.     s[i] += s[i - 1];
  6. }
  7. // 输出[l, r]元素的和
  8. cout << s[r] - s[l - 1] << endl;

二维前缀和

二维前缀和和一维类似。

  1. for (int i = 1; i <= n; i ++) {
  2.     for (int j = 1; j <= m; j ++) {
  3.         cin >> s[i][j];
  4.         // 求解前缀和，s[i][j]表示从(1,1--i,j)子矩阵元素的和
  5.            // 下标从1开始
  6.         s[i][j] = s[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
  7.     }
  8. }
  10. cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl;

差分

差分是前缀和的逆运算。差分数组的前缀和为原数组。
差分可以用O(1)的时间解决某区间的加和问题，即给[l, r]区间内的所有数都加c
求差分数组的时间复杂度为O(n)。

一维差分

差分数组不需要特地用原数组构造，一般通过插入的方式来进行构造。

  1. void insert(int l, int r, int c) {
  2.     b[l] += c;
  3.     b[r + 1] -= c;
  4. }
  6. int main()
  7. {
  8.     cin >> n >> m;
  9.     for (int i = 1; i <= n; i ++) {
  10.         cin >> a[i];
  11.         // 通过插入操作构造差分数组
  12.         insert(i, i, a[i]);
  13.     }
  15.     while(m --) {
  16.         int l, r, c;
  17.         cin >> l >> r >> c;
  18.         // 对[l, r]里的元素加c
  19.         insert(l, r, c);
  20.     }
  23.     for (int i = 1; i <= n; i ++) {
  24.         // 通过求前缀和的方式还原数组
  25.         b[i] += b[i - 1];
  26.         cout << b[i] << " ";
  27.     }
  28.     cout << endl;
  29.     return 0;
  30. }

二维差分

二维差分和一维差分类似。

#include <iostream>
using namespace std;

#define N 1010
int a[N][N], b[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()
{
    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]);
            // 通过插入操作构造差分矩阵
            insert(i, j, i, j, a[i][j]);
        }
    }

    while(q --) {
        int x1, x2, y1, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        // 为子矩阵的元素加c
        insert(x1, y1, x2, y2, c);
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            // 通过前缀和运算还原数组
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            cout << b[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}