前缀和与差分：从原理到实战

1  序言

在高中数列里，我们第一次学到“部分和 (partial sum)”；在程序竞赛里，它以“前缀和 (prefix sum)”之名大放异彩。 而当你需要 区间修改 + 区间查询 时，差分数组 (difference array) 则以极低的代码复杂度给出惊艳解决。二者一静一动，却都建立在“累加”这一朴素思想之上。

2  单维前缀和

2.1  定义

给定序列 $a\_1,a\_2,\dots,a\_n$，其前缀和 $S$ 定义为

$S\_i = \sum\_{k=1}^{i} a\_k,\quad 1\le i\le n.$

显然 $S\_0 = 0$。

2.2  区间求和公式

$\sum\_{k=l}^{r} a\_k = S\_r - S\_{l-1}.$

时空复杂度 ：预处理 O(n)，查询单次 O(1)，空间 O(n)。

2.3  何时使用

• 题目仅 区间求和，无大规模频繁修改。
• 需要尽可能低的常数因子，相比树状数组／线段树更轻量。

---

3  单维差分数组

3.1  定义

设原数组 $a$。差分数组 $d$ 为

$ d\_1 = a\_1,\quad d\_i = a\_i - a\_{i-1};(2\le i\le n). $

易得

$ a\_i = \sum\_{k=1}^{i} d\_k,\quad\text{即 }a= \text{prefix}(d). $

3.2  区间增量修改

若要把区间 $\[l,r]$ 内每个元素都增加 $x$：

d[l]   += x;
d[r+1] -= x;      // 若 r < n

最后一次性做一次前缀和 $O(n)$ 还原 $a$。

3.3  常见模式

• 差分→前缀和：区间修改，最终恢复数值。
• 差分的差分：处理多段线性函数、一次性打标记等进阶技巧。

复杂度 ：每次区间加 O(1)，统一还原 O(n)，总计 O(n+m)。

---

4  二维前缀和与差分

4.1  二维前缀和

令矩阵 $A$ 的二维前缀和 $S$

$ S\_{i,j}=\sum\_{x=1}^{i}\sum\_{y=1}^{j} A\_{x,y}. $

查询子矩阵 $(x\_1,y\_1)-(x\_2,y\_2)$ 的和：

$ \begin{aligned} \text{sum} &= S\_{x\_2,y\_2}-S\_{x\_1-1,y\_2}-S\_{x\_2,y\_1-1}+S\_{x\_1-1,y\_1-1}. \end{aligned} $

4.2  二维差分

若对子矩阵整体加 $v$，则在差分矩阵 $D$ 操作：

D[x1][y1]     += v;
D[x2+1][y1]   -= v;
D[x1][y2+1]   -= v;
D[x2+1][y2+1] += v;

最终对 $D$ 先行列前缀两遍即可得新矩阵。

---

5  前缀和 × 差分的混合技巧

5.1  可并行区间操作

• 区间加，区间和：用差分负责“加”，用前缀和负责“和”，一次扫描即可。
• 差分套差分：处理 “区间加等差数列” 类问题。
• 离散化 + 差分：把稀疏区间放进映射表，内存 O(m)。

5.2  典例：航班预订统计 (LeetCode 1109)

给 m 次操作，每次 [l,r] 加 k，求最后数组。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m;                      // n:座位数, m:操作数
    cin>>n>>m;
    vector<long long>d(n+2,0);
    while(m--){
        int l,r; long long k;
        cin>>l>>r>>k;
        d[l] += k;
        d[r+1] -= k;
    }
    vector<long long>a(n+1,0);
    for(int i=1;i<=n;++i){
        a[i] = a[i-1] + d[i];
        cout<<a[i]<<" \n"[i==n];
    }
    return 0;
}
/*
复杂度:
├─ 时间: O(n+m)
└─ 空间: O(n)
*/

---

6  进阶场景与常见拓展

场景	技巧	备注
树上路径加/求和	树链剖分 + 差分打 tag	空间线性
环形数组	拆环为线性两倍长	注意端点 mod
三维体素计数	三维差分，三重前缀	代码易错
浮点误差	先离散为整数	避免 eps 累积
动态区间最小值	不适合纯前缀/差分，需要线段树

---

7  典型坑点与调试心法

1. 边界 +1 还是 -1？ 配合画数轴／格点示意图。
2. int 溢出 累加量大时用 64 位。
3. 多次 build 差分修改后只在最后一次前缀化，避免重复开销。
4. 二维差分顺序 先行后列或先列后行均可，但全程统一。
5. 在线更新需求 若既要区间加又要多次在线查询，转用树状数组或线段树。

---

8  综合示例：二维区间加与区间和

题目：给 $n!\times!n$ 矩阵，q 次操作：
1 x1 y1 x2 y2 v —— 子矩阵加 $v$
2 x1 y1 x2 y2   —— 查询子矩阵和

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,q; cin>>n>>q;
    vector<vector<ll>> D(n+2, vector<ll>(n+2,0));

    vector<vector<ll>> A;      // 最终矩阵
    vector<tuple<int,int,int,int,int,ll>> queries;

    while(q--){
        int op; cin>>op;
        if(op==1){
            int x1,y1,x2,y2; ll v;
            cin>>x1>>y1>>x2>>y2>>v;
            D[x1][y1]     += v;
            D[x2+1][y1]   -= v;
            D[x1][y2+1]   -= v;
            D[x2+1][y2+1] += v;
        }else{
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            queries.emplace_back(x1,y1,x2,y2,0,0); // 先收集，最后统一回答
        }
    }

    /* --- 构造最终矩阵 A --- */
    A.assign(n+1, vector<ll>(n+1,0));
    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];
            A[i][j]= D[i][j];
        }

    /* --- 预处理二维前缀和 S --- */
    vector<vector<ll>> S(n+1, vector<ll>(n+1,0));
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            S[i][j]=A[i][j]+S[i-1][j]+S[i][j-1]-S[i-1][j-1];

    /* --- 输出所有查询 --- */
    for(auto [x1,y1,x2,y2,_,__]:queries){
        ll ans=S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1];
        cout<<ans<<"\n";
    }
    return 0;
}
/*
时间复杂度:
  预处理 O(n^2)   // 若 n≤1000 足够快
  查询   O(#query)
空间复杂度: O(n^2)
*/

---

9  训练题单

1. CF 190A If at First You Don’t Succeed —— 1D 前缀和入门
2. Luogu P1747 好奇怪系列 —— 1D 差分
3. LeetCode 1109 航班预订统计 —— 区间加
4. POJ 3468 A Simple Problem with Integers —— 线段树 vs. 差分对比
5. AtCoder ABC 045 D – Snuke’s Coloring —— 2D 差分
6. Codeforces 1091F New Year Tree —— 树上差分
7. Kattis – Just Another Board Game —— 三维差分
8. CF 1715E Long Way Home —— 差分套差分，斜率优化