前缀和 与 差分

#include <iostream>
using namespace std;
const int MAXN = 100005;
long long a[MAXN], s[MAXN];

int main() {
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];  // 递推构建前缀和
    }
    while (q--) {
        int l, r; cin >> l >> r;
        cout << s[r] - s[l-1] << "\n";  // O(1) 查询
    }
    return 0;
}

const int MAXN = 1005;
long long a[MAXN][MAXN], s[MAXN][MAXN];

// 预处理
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];

// 查询子矩阵 (x1,y1) 到 (x2,y2) 的和
long long ans = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];

const int MAXN = 100005;
long long a[MAXN], d[MAXN];

// 构造差分数组
for (int i = 1; i <= n; i++)
    d[i] = a[i] - a[i-1];

// 区间 [l, r] 加 v —— O(1)
d[l] += v;
d[r+1] -= v;

// 所有操作完成后，还原原数组
for (int i = 1; i <= n; i++) {
    a[i] = a[i-1] + d[i];  // 对差分数组求前缀和
    cout << a[i] << " ";
}

long long d[MAXN][MAXN];

// 子矩阵 (x1,y1)-(x2,y2) 加 v
d[x1][y1] += v;
d[x1][y2+1] -= v;
d[x2+1][y1] -= v;
d[x2+1][y2+1] += v;

// 还原：对差分数组求二维前缀和
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];
// 此时 d[i][j] 即为最终矩阵 a[i][j]

#include <iostream>
using namespace std;
const int MAXN = 100005;
long long s[MAXN];
int main() {
    ios::sync_with_stdio(0);
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        long long x; cin >> x;
        s[i] = s[i-1] + x;
    }
    while (q--) {
        int l, r; cin >> l >> r;
        cout << s[r] - s[l-1] << "\n";
    }
    return 0;
}

#include <iostream>
using namespace std;
const int MAXN = 100005;
long long d[MAXN];
int main() {
    int n, m; cin >> n >> m;
    while (m--) {
        int l, r; long long v;
        cin >> l >> r >> v;
        d[l] += v;
        d[r+1] -= v;
    }
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += d[i];  // 前缀和还原
        cout << cur << " ";
    }
    cout << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int MAXN = 1005;
long long a[MAXN][MAXN], s[MAXN][MAXN];
int main() {
    ios::sync_with_stdio(0);
    int n, m, q; cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][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;
        cin >> x1 >> y1 >> x2 >> y2;
        long long ans = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
        cout << ans << "\n";
    }
    return 0;
}