18 · 前缀和与差分

两个问题，看着相反，其实是同一件事。

• 问题 A：给 n 个整数，q 次询问“第 l 个到第 r 个的和”。直接 for 累加是 O(nq)，n = q = 10⁵ 时约 5×10⁹ 次加法，TLE。
• 问题 B：给 n 个整数，q 次操作“把第 l 个到第 r 个每个加 z”，最后输出每个数。直接 for 一遍是 O(nq)，同样 TLE。

A 的答案是前缀和：一次 O(n) 预处理，之后每次询问 O(1)。B 的答案是差分：每次修改 O(1)，最后一次 O(n) 还原。两者互为逆运算——前缀和把“一段区间”换成“两个前缀相减”，差分把“一次区间修改”换成“两次单点修改”。

const int MAXN = 200005;                 // 按题目上限开
int n; long long a[MAXN], pre[MAXN];
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];   // O(n) 建表

int q; cin >> q;
while (q--) {
    int l, r; cin >> l >> r;
    cout << pre[r] - pre[l - 1] << "\n";   // O(1) 查询
}

// 目标：把 a[l..r] 每个数都加 z
d[l]     += z;
d[r + 1] -= z;          // r = n 时这句话写的是 d[n+1]，所以要开 n+2

// 撤销差分，把 d 还原成 a
int cur = 0;
for (int i = 1; i <= n; ++i) {
    cur += d[i];        // cur 就是还原后的 a[i]
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000005;      // 题目上限 5×10⁶，再多留几个位给 d[n+1]
int a[MAXN], d[MAXN];          // a 存初始成绩，d 存差分

int main() {
    ios::sync_with_stdio(false);   // 5×10⁶ 个整数，必须提速
    cin.tie(nullptr);

    int n, p;
    cin >> n >> p;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= n; ++i)
        d[i] = a[i] - a[i - 1];    // a[0] 是全局数组，默认 0，所以 d[1] = a[1] 自动成立

    while (p--) {
        int x, y, z;
        cin >> x >> y >> z;
        d[x]     += z;             // 从 x 开始，每个还原值都比原来多 z
        d[y + 1] -= z;             // 从 y+1 开始把这层 z 扣掉，恢复原样
    }

    int cur = 0, mn = INT_MAX;
    for (int i = 1; i <= n; ++i) {
        cur += d[i];               // 前缀和还原：cur 就是最终的 a[i]
        if (cur < mn) mn = cur;    // 边还原边统计最低分，省下第三个数组
    }
    cout << mn << "\n";
    return 0;
}

把数轴换成 n 行 m 列的网格，两类问题照抄：多次询问子矩阵和用二维前缀和；多次矩形加、最后输出整张表用二维差分。区别只有一个：一维里是“两次端点”，二维里是“四个角”。

// 建表：i、j 都必须从小到大（依赖上方和左方）
for (int i = 1; i <= n; ++i)
  for (int j = 1; j <= m; ++j)
    pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];

// 查询子矩阵和
long long s = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];

// 矩形 (x1,y1)-(x2,y2) 每个格子加 z
d[x1][y1]         += z;
d[x2 + 1][y1]     -= z;
d[x1][y2 + 1]     -= z;
d[x2 + 1][y2 + 1] += z;

// 还原：做完这一步 d[i][j] 才是格子 (i,j) 的真实值
for (int i = 1; i <= n; ++i)
  for (int j = 1; j <= m; ++j)
    d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];

S = [1 0 0]      D = [ 1  0 0]        D * S = I
    [1 1 0]          [-1  1 0]
    [1 1 1]          [ 0 -1 1]

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;         // n ≤ 1000，还要用下标 n+1，所以多开几个
int d[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);   // n² = 10⁶ 次输出，必须提速
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    while (m--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        d[x1][y1]         += 1;    // 左上角：从这里开始算被覆盖
        d[x2 + 1][y1]     -= 1;    // 下边界之外一行：撤掉
        d[x1][y2 + 1]     -= 1;    // 右边界之外一列：撤掉
        d[x2 + 1][y2 + 1] += 1;    // 右下角外侧被撤了两次，补回一次
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];  // 二维前缀和还原
            cout << d[i][j] << (j == n ? '\n' : ' ');
        }
    }
    return 0;
}