前缀和与差分CSP-J

💡 核心思想

前缀和是一种预处理技巧，用 $O(n)$ 预处理后可以在 $O(1)$ 时间内查询任意区间的元素之和。差分是前缀和的逆运算，用于 $O(1)$ 区间修改、$O(n)$ 查询最终结果。

🎯 直觉理解

前缀和就像记账：你记下"到第 i 天为止总共花了多少钱"，那"第3天到第7天花了多少"就是"到第7天的总额 - 到第2天的总额"。差分就像"我今天比昨天多花了10块"——知道每天的差值就能还原每天的总额。

📝 算法流程

1. 一维前缀和：$s[i] = s[i-1] + a[i]$，区间和 $[l,r] = s[r] - s[l-1]$
2. 一维差分：$d[l]+=v, d[r+1]-=v$，最后求前缀和还原
3. 二维前缀和：容斥原理
4. 二维差分：四个角操作

$$\sum_{i=l}^{r} a[i] = s[r] - s[l-1]$$

$$\text{差分：} d[l] \mathrel{+}= v,\ d[r+1] \mathrel{-}= v$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, q; cin >> n >> q;
    vector<long long> a(n+2, 0), s(n+1, 0);
    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";
    }
    // 差分数组示例
    vector<long long> d(n+2, 0);
    // 区间 [l, r] 加 v
    auto add = [&](int l, int r, long long v) { d[l] += v; d[r+1] -= v; };
    // 还原：对 d 求前缀和
    return 0;
}

⚠️ 常见坑点

📚 相关题目