// 构建前缀和数组 — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 第一步：读取输入（1-indexed）
    vector<int> A(n + 1);
    for (int i = 1; i <= n; i++) cin >> A[i];

    // 第二步：构建前缀和
    vector<long long> P(n + 1, 0);  // P[0] = 0（基础情况）
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] + A[i];   // ← 关键行：每个 P[i] = 到 i 为止所有元素之和
    }

    return 0;
}

// 区间求和查询 — 预处理 O(N)，每次查询 O(1)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
long long A[MAXN];
long long P[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    // 第一步：读取数组
    for (int i = 1; i <= n; i++) cin >> A[i];

    // 第二步：构建前缀和 — O(n)
    P[0] = 0;
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] + A[i];
    }

    // 第三步：回答 q 个区间求和查询 — 每次 O(1)
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << P[r] - P[l - 1] << "\n";  // ← 关键行：区间和公式
    }

    return 0;
}

// 多品种前缀和 — O(N + Q)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<int> breed(n + 1);
    vector<vector<long long>> P(4, vector<long long>(n + 1, 0));
    // P[b][i] = 位置 1..i 中品种 b 的奶牛数量

    // 第一步：为每种品种构建前缀和
    for (int i = 1; i <= n; i++) {
        cin >> breed[i];
        for (int b = 1; b <= 3; b++) {
            P[b][i] = P[b][i - 1] + (breed[i] == b ? 1 : 0);  // ← 关键行
        }
    }

    // 第二步：每次查询 O(1) 回答
    for (int i = 0; i < q; i++) {
        int l, r, b;
        cin >> l >> r >> b;
        cout << P[b][r] - P[b][l - 1] << "\n";
    }

    return 0;
}

// FJ 的草地 — 前缀和解法 O(N + Q)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    // 第一步：读取草量并同步构建前缀和
    vector<long long> P(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long g;
        cin >> g;
        P[i] = P[i - 1] + g;   // ← 关键行：增量前缀和
    }

    // 第二步：每次查询 O(1) 回答
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << P[r] - P[l - 1] << "\n";
    }

    return 0;
}

P[1][1] = A[1][1] = 1
P[1][2] = 2 + 0 + 1 - 0 = 3
P[1][3] = 3 + 0 + 3 - 0 = 6
P[1][4] = 4 + 0 + 6 - 0 = 10
P[2][1] = 5 + 1 + 0 - 0 = 6
P[2][2] = 6 + 3 + 6 - 1 = 14
P[2][3] = 7 + 6 + 14 - 3 = 24
P[2][4] = 8 + 10 + 24 - 6 = 36
P[3][1] = 9 + 6 + 0 - 0 = 15
P[3][2] = 10 + 14 + 15 - 6 = 33
P[3][3] = 11 + 24 + 33 - 14 = 54
P[3][4] = 12 + 36 + 54 - 24 = 78
P[4][1] = 13 + 15 + 0 - 0 = 28
P[4][2] = 14 + 33 + 28 - 15 = 60
P[4][3] = 15 + 54 + 60 - 33 = 96
P[4][4] = 16 + 78 + 96 - 54 = 136

// 二维前缀和 — 构建 O(R×C)，查询 O(1)
#include <bits/stdc++.h>
using namespace std;

const int MAXR = 1001, MAXC = 1001;
int A[MAXR][MAXC];
long long P[MAXR][MAXC];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int R, C;
    cin >> R >> C;

    for (int r = 1; r <= R; r++)
        for (int c = 1; c <= C; c++)
            cin >> A[r][c];

    // 第一步：构建二维前缀和 — O(R × C)
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            P[r][c] = A[r][c]
                    + P[r-1][c]    // 上方矩形
                    + P[r][c-1]    // 左方矩形
                    - P[r-1][c-1]; // ← 关键行：消除重叠（被计算了两次）
        }
    }

    // 第二步：每次查询 O(1) 回答
    int q;
    cin >> q;
    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        long long ans = P[r2][c2]
                      - P[r1-1][c2]    // 减去上方条带
                      - P[r2][c1-1]    // 减去左方条带
                      + P[r1-1][c1-1]; // 加回左上角
        cout << ans << "\n";
    }

    return 0;
}

// 差分数组实现区间更新 — O(N + M)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    // diff[i] 表示从位置 i 开始，当前值发生了多少变化
    // 多开 1 位：当更新区间右端点 r = n 时，需要访问 diff[n + 1]
    vector<long long> diff(n + 2, 0);

    // 第一步：处理所有区间更新
    for (int i = 0; i < m; i++) {
        int l, r;
        long long v;
        cin >> l >> r >> v;

        diff[l] += v;      // 从 l 开始，增加 v 生效
        diff[r + 1] -= v;  // 从 r+1 开始，取消这次增加
    }

    // 第二步：对 diff 做前缀和，得到最终数组
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        cout << cur;
        if (i < n) cout << " ";
    }
    cout << "\n";

    return 0;
}

// 二维差分数组 — 每次矩形更新 O(1)，最终重建 O(R × C)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int R, C, M;
    cin >> R >> C >> M;

    // 多开一圈哨兵：当 r2=R 或 c2=C 时，会访问 r2+1 或 c2+1
    vector<vector<long long>> diff(R + 2, vector<long long>(C + 2, 0));

    // 第一步：每次 O(1) 标记一个矩形更新
    while (M--) {
        int r1, c1, r2, c2;
        long long v;
        cin >> r1 >> c1 >> r2 >> c2 >> v;

        diff[r1][c1]         += v;
        diff[r1][c2 + 1]     -= v;
        diff[r2 + 1][c1]     -= v;
        diff[r2 + 1][c2 + 1] += v;
    }

    // 第二步：二维前缀和重建最终网格
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            diff[r][c] += diff[r - 1][c]
                        + diff[r][c - 1]
                        - diff[r - 1][c - 1];
        }
    }

    // 第三步：输出最终网格
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            cout << diff[r][c];
            if (c < C) cout << " ";
        }
        cout << "\n";
    }

    return 0;
}

// Kadane 算法 — O(N) 时间，O(1) 空间
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    // Kadane 算法：O(n)
    long long maxSum = LLONG_MIN;  // 最小 long long
    long long current = 0;

    for (int i = 0; i < n; i++) {
        current += A[i];
        maxSum = max(maxSum, current);
        if (current < 0) current = 0;  // ← 关键行：和为负时重新开始
    }

    cout << maxSum << "\n";

    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // USACO 官方文件 I/O 可按需打开：
    // freopen("bcount.in", "r", stdin);
    // freopen("bcount.out", "w", stdout);

    int n, q;
    cin >> n >> q;

    vector<array<int, 4>> prefix(n + 1);  // 只使用下标 1..3

    for (int i = 1; i <= n; i++) {
        int breed;
        cin >> breed;
        prefix[i] = prefix[i - 1];        // 继承前 i-1 头的计数
        prefix[i][breed]++;               // 当前品种加 1
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        for (int b = 1; b <= 3; b++) {
            int count = prefix[r][b] - prefix[l - 1][b];
            cout << count << " \n"[b == 3];
        }
    }

    return 0;
}

复杂度： 预处理 O(N × 3)，每次查询 O(3)，总复杂度 O(N+Q)，空间 O(3N)。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // USACO 官方文件 I/O 可按需打开：
    // freopen("stacking.in", "r", stdin);
    // freopen("stacking.out", "w", stdout);

    int n, k;
    cin >> n >> k;

    vector<int> diff(n + 2, 0);  // 需要写到 b+1，最大可能是 n+1

    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        diff[a] += 1;
        diff[b + 1] -= 1;
    }

    vector<int> height(n + 1);
    int current = 0;
    for (int i = 1; i <= n; i++) {
        current += diff[i];
        height[i] = current;
    }

    sort(height.begin() + 1, height.end());
    cout << height[(n + 1) / 2] << "\n";  // n 为奇数，中位数下标固定

    return 0;
}

复杂度： 区间更新 O(K)，重建 O(N)，排序 O(N log N)，空间 O(N)。

核心思路： O(N) 预计算前缀和，每次查询 O(1) 回答 P[R] - P[L-1]。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; cin >> n >> q;
    vector<long long> P(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        P[i] = P[i-1] + x;
    }
    while (q--) {
        int l, r; cin >> l >> r;
        cout << P[r] - P[l-1] << "\n";
    }
}

复杂度： O(N + Q) —— 远好于朴素 O(N × Q)。

核心思路： 差分数组。每次区间加法只影响 diff 的 2 个位置，最终值通过前缀和得到。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<long long> diff(n + 2, 0);
    while (m--) {
        int l, r; long long v; cin >> l >> r >> v;
        diff[l] += v;
        diff[r+1] -= v;
    }
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        cout << cur << " \n"[i == n];
    }
}

复杂度： O(N + M) —— 每次更新 O(1)，最后扫描 O(N)。

核心思路： 二维前缀和。P[i][j] = 从 (1,1) 到 (i,j) 的矩形和，对任意矩形查询用容斥相减。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m, q; cin >> n >> m >> q;
    vector<vector<long long>> P(n+1, vector<long long>(m+1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x; cin >> x;
            P[i][j] = x + P[i-1][j] + P[i][j-1] - P[i-1][j-1];
        }
    while (q--) {
        int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
        cout << P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1] << "\n";
    }
}

复杂度： O(N × M + Q)。

核心思路： 直接模拟——不需要复杂数据结构。沿路径走，对每个访问的格子递增二维计数器。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    map<pair<int,int>, int> cnt;
    int x = 0, y = 0; cnt[{x,y}]++;
    while (n--) {
        char dir; int steps; cin >> dir >> steps;
        int dx = (dir=='E') - (dir=='W');
        int dy = (dir=='N') - (dir=='S');
        while (steps--) {
            x += dx; y += dy;
            cnt[{x,y}]++;
        }
    }
    int doubleMowed = 0;
    for (auto& [pos, c] : cnt) if (c >= 2) doubleMowed++;
    cout << doubleMowed << "\n";
}

复杂度： O(总步数 × log)，受 map 操作主导。

核心思路： 二维差分数组。每次矩形更新只触及 4 个角。最终网格 = 差分数组的二维前缀和。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, q; cin >> n >> m >> q;
    vector<vector<long long>> D(n+2, vector<long long>(m+2, 0));
    while (q--) {
        int r1, c1, r2, c2; long long v;
        cin >> r1 >> c1 >> r2 >> c2 >> v;
        D[r1][c1] += v;
        D[r1][c2+1] -= v;
        D[r2+1][c1] -= v;
        D[r2+1][c2+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];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cout << D[i][j] << " \n"[j == m];
}

复杂度： O(Q + N × M)。

核心思路： 在每个位置，要么开始新的子数组，要么延伸当前的。cur = max(A[i], cur + A[i])，追踪最优值。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    long long best = LLONG_MIN, cur = 0;
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        cur = max(x, cur + x);
        best = max(best, cur);
    }
    cout << best << "\n";
}

为什么当 cur+x < x 时从头开始？ 因为负的运行和只会损害未来的项——丢弃它，从当前元素重新开始。

追踪 [-2, 1, -3, 4, -1, 2, 1, -5, 4]：

x=-2: cur=-2, best=-2
x=1:  cur=max(1,-2+1)=1, best=1
x=-3: cur=max(-3,1-3)=-2, best=1
x=4:  cur=max(4,-2+4)=4, best=4
x=-1: cur=max(-1,4-1)=3, best=4
x=2:  cur=5, best=5
x=1:  cur=6, best=6 ✓
x=-5: cur=1, best=6
x=4:  cur=5, best=6

复杂度： O(N) 时间，O(1) 空间。

核心思路： 每次区间加法只改两个位置：diff[L] += V，diff[R+1] -= V。最后扫描时，当前前缀和就是当前位置的最终值。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<long long> diff(n + 2, 0);

    while (m--) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        diff[l] += v;
        diff[r + 1] -= v;
    }

    long long cur = 0;
    long long best = LLONG_MIN;

    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        best = max(best, cur);
    }

    cout << best << "\n";
    return 0;
}

复杂度： O(N + M) 时间，O(N) 空间。

核心思路： 这题不是要求输出最终数组，而是要求统计满足条件的位置数。差分数组恢复时顺手统计即可。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<int> diff(n + 2, 0);

    while (m--) {
        int l, r;
        cin >> l >> r;
        diff[l] += 1;
        diff[r + 1] -= 1;
    }

    int cur = 0;
    int answer = 0;

    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        if (cur >= k) answer++;
    }

    cout << answer << "\n";
    return 0;
}

复杂度： O(N + M) 时间，O(N) 空间。

核心思路： 最简单的写法是：diff 只记录所有操作带来的增量。最后扫描 diff 得到当前位置总共增加了多少，再加到 A[i] 上。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<long long> diff(n + 2, 0);

    while (m--) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        diff[l] += v;
        diff[r + 1] -= v;
    }

    long long add = 0;
    for (int i = 1; i <= n; i++) {
        add += diff[i];
        cout << a[i] + add << " \n"[i == n];
    }

    return 0;
}

复杂度： O(N + M) 时间，O(N) 空间。

核心思路： 二维差分的四角标记是 + - - +。恢复时使用二维前缀和公式：D[r][c] += D[r-1][c] + D[r][c-1] - D[r-1][c-1]。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int R, C, M, K;
    cin >> R >> C >> M >> K;

    vector<vector<int>> diff(R + 2, vector<int>(C + 2, 0));

    while (M--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;

        diff[r1][c1] += 1;
        diff[r1][c2 + 1] -= 1;
        diff[r2 + 1][c1] -= 1;
        diff[r2 + 1][c2 + 1] += 1;
    }

    int answer = 0;

    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            diff[r][c] += diff[r - 1][c]
                        + diff[r][c - 1]
                        - diff[r - 1][c - 1];
            if (diff[r][c] >= K) answer++;
        }
    }

    cout << answer << "\n";
    return 0;
}

复杂度： O(R × C + M) 时间，O(R × C) 空间。

1. 前缀和。 数组不变，多次区间和查询，预处理后每次 O(1)。
2. 一维差分数组。 多次区间加法，最后统一恢复结果。
3. 树状数组或线段树。 更新和查询交替出现，普通差分数组无法直接处理中途查询。
4. 二维差分数组。 矩形区域批量加值，最后统一重建网格。

这道题的重点不是写代码，而是学会从题面信号中判断该用哪种工具。

朴素枚举所有 O(N²M²) 矩形对 500² 来说太慢。改进方案：

1. 用二维前缀和实现 O(1) 求和查询
2. 对子网格中的最大值：预处理二维稀疏表（或每行 RMQ）实现 O(1) 最大值查询
3. 边界和 = 总和 - 内部和（均通过前缀和）

总计：O(N²M²) 枚举 × O(1) 每次查询 = 对 N,M ≤ 500 在时间限制内。