前缀和与差分

前缀和把重复的区间查询预处理为端点相减；差分把区间修改转化为端点修改。二者互为逆运算：数组的前缀和是累计结果，差分是相邻元素之差。

一维前缀和

采用 1 下标时令 s[0]=0，s[i]=s[i-1]+a[i]。闭区间 [l,r] 的和为 s[r]-s[l-1]，预处理 O(n)，每次查询 O(1)。区间和可能溢出 int，应使用 long long。

vector<long long> s(n + 1);
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
auto rangeSum = [&](int l, int r) { return s[r] - s[l - 1]; };

一维差分

令 d[i]=a[i]-a[i-1]。给整个 [l,r] 加 c 时，只需 d[l]+=c、d[r+1]-=c；所有修改完成后对差分数组求前缀和即可恢复最终数组。数组需开出 r+1 的哨兵位置。

vector<long long> d(n + 2);
auto add = [&](int l, int r, long long c) {
    d[l] += c;
    d[r + 1] -= c;
};
for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + d[i];

二维前缀和与差分

二维前缀和满足 s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]。矩形 (x1,y1)~(x2,y2) 的和为 s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]。

二维差分对矩形加 c 时，在四个角分别执行 +c、-c、-c、+c，再做二维前缀和恢复。下标边界和容器大小是最常见错误。

适用范围

静态数组的多次区间查询适合前缀和；大量区间修改、最后统一取结果适合差分。若查询与修改交替在线发生，可使用树状数组或线段树；树上的子树和、路径修改也常借助 DFS 序或树上差分转化为数组问题。