前缀和与差分

YZY Lv3
  2025-06-17 22:06:49 2025-06-17 22:06:49 Created   2025-06-17 22:06:49 2025-06-17 22:06:49 Updated      

序言

在算法竞赛的征途中，决定成败的，有时并非是那些深奥的理论，而在于对基础思想的极致运用。前缀和与差分，便是这样一种返璞归真的利器。它们的核心，在于一种优雅的视角转换：将耗时的“范围处理”转化为瞬时的“端点操作”。这一看似简单的思想，却蕴含着惊人的能量，能将许多问题的复杂度直接降低一个乃至数个量级。

第一章：一维前缀和

1.1 定义与核心思想

前缀和，顾名思义，是“前缀”的“和”。对于一个给定的数组，我们定义其前缀和数组如下：

表示原数组中从第 1 个元素到第个元素的总和。

用数学语言来表达，就是：

为了方便处理，我们通常让数组下标从 1 开始。这有一个非常重要的好处，即可以自然地定义为 0，这能极大地简化后续区间的计算。

核心思想：通过的时间预处理出前缀和数组，从而能够以的时间复杂度回答任意区间的和查询。这是一种典型的 空间换时间 的策略。

前缀和的构造过程是一个简单的递推：

这个递推关系是前缀和算法的基石。

1.2 核心操作：区间查询

前缀和的威力体现在区间查询上。假设我们需要查询数组在闭区间内所有元素的和，即。

直接计算需要遍历从到的所有元素，时间复杂度为，在最坏情况下是。对于多组查询，这种朴素方法是无法接受的。

利用前缀和数组，我们可以将这个求和过程变得极为高效。观察一下：

两式相减，奇迹发生了：

这个公式是前缀和的灵魂。它告诉我们，任意一个区间的和，都可以通过前缀和数组的两个元素的差来表示。预处理之后，每次查询都只需要一次减法运算，时间复杂度是惊人的。

注意：这正是我们推荐使用 1-based 索引的原因。如果使用 0-based 索引，查询区间的和将是（当时）和（当时），需要进行分情况讨论，增加了代码的复杂性和出错的可能。在 1-based 索引下，天然为 0，公式对所有的情况都统一适用了。

1.3 代码实现与典型应用

让我们来看一个最经典的应用场景。

题意概括:
给定一个长度为的数组和次查询。每次查询给出一个区间，要求输出到的和。
。

这是一个模板题，完美地展示了前缀和的优势。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100005;
int n, m;
int a[N];
ll s[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    // 预处理前缀和数组 s
    // s[0] 默认为 0
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i-1] + a[i];
    }

    while (m--) {
        int l, r;
        cin >> l >> r;
        // O(1) 查询
        cout << s[r] - s[l-1] << "\n";
    }

    return 0;
}

复杂度分析:

  • 时间复杂度: 。其中用于预处理前缀和数组，之后的次查询每次仅需时间。
  • 空间复杂度: 。用于存储前缀和数组。

这段代码虽然简单，但它体现了算法竞赛中的一个核心思想：如果一个计算过程会被重复多次，并且该过程的输入相对固定，那么就应该考虑预处理。

第二章：一维差分 - 静态世界的动态修改

如果说前缀和是为“查询”而生，那么差分就是为“修改”而生，尤其是区间修改。差分和前缀和是一对互逆的操作，理解它们的对偶关系，是掌握其精髓的关键。

2.1 定义与核心思想

对于一个给定的数组，我们定义其差分数组如下（同样，我们采用 1-based 索引）：

  • (for )

换句话说，差分数组记录的是原数组中相邻元素的差值。

核心思想：差分数组的前缀和就是原数组。即：

为什么？我们可以简单推导一下：


这个性质是连接差分和前缀和的桥梁。它告诉我们，对差分数组做前缀和，就可以还原出原数组。

2.2 核心操作：区间修改

差分的真正威力在于处理区间修改。假设我们需要对数组的一个区间上的每个元素都加上一个值。

朴素的做法是遍历从到的所有元素，逐个加上，时间复杂度为。如果需要进行次这样的修改，总复杂度会达到，这通常是不可接受的。

现在，我们来观察这个操作对差分数组造成了什么影响：

  1. **对于**：它的值变成了。由于，新的将变为。所以，增加了。

  2. 对于区间内的任意元素 ()：它的值变成了。同时，它前面的元素也变成了。那么新的差分值为。所以，这些位置的差分值没有变化。

  3. **对于**：它的值没有变，但是它前面的元素变成了。新的差分值将变为。所以，减少了。

  4. 对于其他位置：其自身和前一个元素的值都未改变，因此差分值也不变。

结论：对原数组的区间加上一个值，这个操作等价于对差分数组进行两个单点修改：

这个转换是革命性的。它将一个的区间操作，变成了两个的单点操作。

2.3 从差分到原数组

经过多次区间修改后，差分数组记录了所有的变化。如果我们想知道最终的原数组是什么样子，只需要根据这个关系，对差分数组求一遍前缀和即可。

整个流程如下：

  1. 根据初始数组，构造出初始差分数组。()
  2. 对于每一次区间加的操作，执行和。( for each query)
  3. 所有修改操作结束后，对差分数组求前缀和，还原出最终的数组。()

这个技巧适用于离线处理所有修改，然后一次性求出最终结果的场景。

2.4 代码实现与典型应用

题意概括:
给定一个长度为的初始全为 0 的数组。接下来有次操作，每次操作将指定区间内的所有数都加上。最后，输出整个数组。
。

这个问题是差分算法的直接应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100005;
int n, m;
// a 是原数组，d 是差分数组
ll a[N], d[N];

void add(int l, int r, int c) {
    d[l] += c;
    d[r + 1] -= c;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    // 初始数组全为0, 其差分数组也全为0, 无需显式构造
    // 如果初始数组不为0, 需要先根据初始数组a构造d
    // for(int i=1; i<=n; ++i) cin >> a[i];
    // for(int i=1; i<=n; ++i) d[i] = a[i] - a[i-1];
    
    while (m--) {
        int l, r, c;
        cin >> l >> r >> c;
        add(l, r, c); // O(1) 修改
    }

    // 通过前缀和还原数组 a
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i-1] + d[i]; // a 此时可以看作 d 的前缀和数组
    }

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

    return 0;
}

复杂度分析:

  • 时间复杂度: 。次修改操作，每次，总共。最后还原数组需要。
  • 空间复杂度: 。用于存储差分数组和最终的数组。

这个模型在比赛中非常常见，比如模拟对一段连续的区间进行染色、增加属性值等。当你看到“对区间进行某种操作”并且查询次数不多或者只在最后查询时，差分思想就应该浮现在你的脑海中。

第三章：二维世界的延伸

一维的技巧虽然强大，但竞赛的世界是多维的。将前缀和与差分的思想推广到二维，是选手能力进阶的重要一步。二维的推导比一维要复杂，但其核心思想——容斥原理。

3.1 二维前缀和

3.1.1 定义与递推公式

与一维类似，二维前缀和定义为从左上角到右下角这个矩形区域内所有元素的和。

如何高效地计算？直接遍历求和显然是低效的。我们需要一个递推公式。

想象一下计算的过程。我们想利用已经计算好的、更小的矩形的和。
所代表的区域，可以看作是：

  1. 左边的矩形区域
  2. 上方的矩形区域
  3. 再加上当前元素

但是，当我们把和相加时，左上角的区域被加了两次。根据容斥原理，我们需要减去这个重复计算的部分。

因此，我们得到了二维前缀和的递推公式：

这个公式是二维前缀和的核心。通过它，我们可以在的时间内预处理出整个二维前 “缀” 和（或者说“前缀矩形和”）矩阵。

(为了计算大矩形的和，我们将上面和左边的矩形相加，这导致左上角的小矩形被加了两次，所以需要减掉一次)

3.1.2 查询公式

二维前缀和的终极目标，是在时间内查询任意一个子矩形的和。假设我们需要查询以为左上角，以为右下角的矩形区域内所有元素的和。

同样，我们将利用容斥原理，通过已经计算好的“前缀矩形”来拼凑出目标矩形。

  1. 首先，我们取右下角为的大矩形。这个矩形包含了我们想要的区域，但也多出了一些部分。
  2. 我们需要减去目标矩形上方的多余部分，即以为右下角的矩形，其和为。
  3. 我们还需要减去目标矩形左方的多余部分，即以为右下角的矩形，其和为。
  4. 此时，我们发现，左上角以为右下角的矩形，既被步骤2减了一次，又被步骤3减了一次，它被多减了。因此，需要把它加回来。这个矩形的和是。

综上，我们得到了子矩形求和的公式：

这个公式完美地体现了容斥原理，并且将子矩形查询的复杂度降至。

3.1.3 代码实现与应用

题意概括:
给定一个的矩阵和次查询。每次查询给出一个子矩形的左上角坐标和右下角坐标，要求输出该子矩形内所有元素的和。
, 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1005;
int n, m, k;
int a[N][N];
ll s[N][N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }

    // 预处理二维前缀和
    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];
        }
    }

    while (k--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // O(1) 查询
        ll ans = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
        cout << ans << "\n";
    }

    return 0;
}

复杂度分析:

  • 时间复杂度: 。其中用于预处理，之后的次查询每次仅需。
  • 空间复杂度: 。用于存储前缀和矩阵。

3.2 二维差分

二维差分是一维差分的自然推广，但其思想的跳跃性更大，是许多选手容易混淆的难点。其目标同样是将矩形区域的修改转化为常数次单点修改。

3.2.1 思想的飞跃

回忆一下一维差分：对区间加，等价于和。其本质是，在处引入一个增量，这个增量会通过前缀和一直向后影响；然后在处引入一个，以抵消从开始的后续影响，从而将影响范围精确地限制在内。

二维差分也遵循这个“引入增量，并在影响范围之外取消增量”的思想。

我们定义二维差分矩阵，使得原矩阵是的二维前缀和。也就是说：

这个关系反过来也成立，即是的“二维差分”，具体的构造方法是：
。这恰好是二维前缀和递推公式的逆运算。

3.2.2 核心操作：矩形修改

假设我们要对以为左上角，为右下角的矩形区域内所有元素都加上一个值。

我们希望通过修改差分矩阵上的几个点，使得在对求二维前缀和（还原）时，效果恰好是目标矩形区域增加了，而其他区域不变。

让我们再次借助容斥原理，思考如何构造这个修改。
为了让右下方的所有元素都加上，我们可以在处加上。

经过这个修改后，当我们计算前缀和时，对于任意，其值都会包含这个的增量。这影响的范围太大了。

我们需要在不希望被影响的区域，把这个的影响去掉。

  1. 在轴方向上，影响不应超过。所以在这一列的开头，即处，我们需要引入一个来抵消。
  2. 在轴方向上，影响不应超过。所以在这一行的开头，即处，我们也需要引入一个来抵消。
  3. 但是，我们引入的两个的操作，在右下方的区域会同时生效。这意味着，对于的区域，总增量变成了。而我们期望的增量是。为了修正这个问题，我们需要在处再引入一个。

这四个操作合在一起，就精确地将影响控制在了目标矩形之内。

结论：对原矩阵的矩形区域加上一个值，等价于对差分矩阵进行四个单点修改：

这四个点恰好是目标矩形及其影响范围边界的四个“角点”。这与二维前缀和的子矩形求和公式中的四个点遥相呼应，再次体现了它们之间的对偶性。

3.2.3 代码实现与应用

题意概括:
给定一个的初始全为 0 的矩阵。接下来有次操作，每次操作将指定的子矩形内的所有数都加上。最后，输出整个矩阵。
, 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1005;
int n, m, k;
// a 是原矩阵, d 是差分矩阵
ll a[N][N], d[N][N];

// 对差分矩阵进行修改
void add(int x1, int y1, int x2, int y2, int c) {
    d[x1][y1] += c;
    d[x2 + 1][y1] -= c;
    d[x1][y2 + 1] -= c;
    d[x2 + 1][y2 + 1] += c;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;
    // 初始矩阵全为0, 差分矩阵也全为0, 无需构造
    // 如果初始矩阵a不为0, 需要先构造差分矩阵d:
    // for (int i = 1; i <= n; ++i) {
    //     for (int j = 1; j <= m; ++j) {
    //         // 假设已读入a[i][j]
    //         add(i, j, i, j, a[i][j]); 
    //     }
    // }
    // 上述构造方法是利用add函数，更直接的构造是 d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

    while (k--) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        add(x1, y1, x2, y2, c); // O(1) 修改
    }

    // 通过二维前缀和从差分矩阵还原原矩阵
    // a[i][j] 实际上是 d 的二维前缀和
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + d[i][j];
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

复杂度分析:

  • 时间复杂度: 。次矩形修改，每次，总共。最后通过二维前缀和还原矩阵需要。
  • 空间复杂度: 。用于存储差分矩阵和最终的矩阵。

第四章：动态世界 - 与数据结构的联系

我们目前讨论的差分模型，其工作模式是“批量修改，单次查询”。即，我们先接受所有修改操作，最后通过一次的前缀和来得到最终结果。这种离线处理方式在很多场景下已经足够。

但如果问题要求在线处理呢？也就是说，修改操作和查询操作是交错进行的。我们每做一次区间修改后，都可能需要立即回答某个点的值，或者某个区间的和。此时，每次修改后都花费重构前缀和，总复杂度将无法承受。

这正是更高级的数据结构——树状数组（Fenwick Tree, or BIT）和线段树（Segment Tree）——大显身手的舞台。而前缀和与差分的思想，恰恰是驾驭这些数据结构的底层逻辑。

4.1 前缀和与树状数组：天作之合

树状数组本身就是一种“动态前缀和”的利器。它被设计用来在的时间内完成两件事：

  1. 单点修改：修改原数组中一个元素的值。
  2. 前缀查询：查询原数组在区间的前缀和。

当你需要动态维护一个数组的前缀和时，树状数组是你的不二之选。它通过操作，将任意一个前缀巧妙地拆分成个不相交的区间，从而实现了查询和修改的平衡。

一个标准的树状数组应用场景如下：

  • : 将加上。这需要更新树状数组中所有包含的节点，时间复杂度。
  • : 查询。这需要累加树状数组中代表的若干个区间节点，时间复杂度。

利用，查询区间的和就变成了，与静态前缀和的公式完全一致，只是每次查询的代价从变成了。

由于树状数组本身就是前缀和的动态化身，其内容与本篇主旨有重叠但并非核心，我们在此不展开其内部实现，而是聚焦于差分思想如何与树状数组结合，产生更强大的化学反应。

4.2 差分与树状数组：优雅的降维打击

真正的魔法发生在我们将差分数组搬到树状数组上时。

思考一个经典问题：支持区间修改，单点查询。

  • 操作一：将区间的所有元素加上。
  • 操作二：查询的当前值。

我们已经知道，区间加等价于在差分数组上做两次单点修改：和。
而查询的值，根据定义，等于其差分数组的前缀和：。

发现了吗？

  • 区间修改 两次单点修改
  • 单点查询 一次前缀和查询

这个转换太美妙了！问题被完美地转化成了可以用树状数组高效处理的“单点修改”和“前缀和查询”。我们只需要用一个树状数组来维护差分数组即可。

  • 完成一次区间修改。每次。
  • 完成一次单点查询。每次。

题意概括:
给定一个长度为的数组，初始全为 0。进行次操作，操作分为两种：

  1. : 将区间内所有数加上。
  2. : 查询的值。
    。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100005;
int n, m;
ll t[N]; // 树状数组, 维护差分数组d

// 树状数组单点加
void add(int x, ll c) {
    for (; x <= n; x += x & -x) t[x] += c;
}

// 树状数组前缀和查询
ll sum(int x) {
    ll res = 0;
    for (; x; x -= x & -x) res += t[x];
    return res;
}

// 区间加
void radd(int l, int r, int c) {
    add(l, c);
    if (r + 1 <= n) add(r + 1, -c);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    // 假设初始数组不为0, 需要先处理
    // for(int i=1; i<=n; ++i) {
    //     cin >> a[i];
    //     radd(i, i, a[i]); // 初始每个a[i]看作一次区间[i,i]的修改
    // }

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r, c;
            cin >> l >> r >> c;
            radd(l, r, c);
        } else {
            int x;
            cin >> x;
            // a[x] = sum of d[1]..d[x]
            cout << sum(x) << "\n";
        }
    }

    return 0;
}

复杂度分析:

  • 时间复杂度: 。每次操作（无论是区间修改还是单点查询）都转化为树状数组上的操作。
  • 空间复杂度: 。用于存储树状数组。

4.3 双树状数组下的区间修改与区间查询

这是前缀和与差分思想应用的顶峰之一。问题升级为：支持区间修改，区间查询。

我们已经知道如何用一个树状数组维护差分数组来实现区间修改。现在的问题是，如何计算区间的和，即？

这等价于计算(sum of a[1..r]) - (sum of a[1..l-1])。我们只需要解决如何计算的前缀和。

回忆。那么的前缀和就是：

这个双重求和的式子直接计算起来很麻烦。我们需要对它进行变形。考虑每个对总和的贡献。会在中出现，共出现了次。
因此，上式可以改写为：

展开括号，得到：

观察这个最终的公式。它把的前缀和查询，转化为了两个部分的差：

  1. ：这是差分数组的前缀和。
  2. ：这是一个新数组的前缀和，其中。

这两个部分都是标准的前缀和查询形式！我们可以用两个树状数组来分别维护它们：

  • 第一个树状数组，维护。
  • 第二个树状数组，维护。

当进行区间加的操作时：

  • , 。
  • 对应到，是和。
  • 对应到，是和。

当查询的前缀和时：

  • 结果为。

有了计算前缀和的方法，区间和就可以通过得到。

题意概括:
“P3374 【模板】树状数组 1” 的升级版，支持区间加法和区间求和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100005;
int n, m;
ll t1[N], t2[N]; // t1维护d[i], t2维护i*d[i]

void add(ll t[], int x, ll c) {
    for (; x <= n; x += x & -x) t[x] += c;
}

ll sum(ll t[], int x) {
    ll res = 0;
    for (; x; x -= x & -x) res += t[x];
    return res;
}

void radd(int l, int r, ll c) {
    add(t1, l, c);
    add(t1, r + 1, -c);
    add(t2, l, l * c);
    add(t2, r + 1, -(r + 1) * c);
}

ll psum(int x) {
    if (x == 0) return 0;
    ll s1 = sum(t1, x);
    ll s2 = sum(t2, x);
    return (x + 1) * s1 - s2;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    ll prev = 0;
    for (int i = 1; i <= n; ++i) {
        ll cur;
        cin >> cur;
        radd(i, i, cur - prev); // 初始值可看作差分值
        prev = cur;
    }

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            ll c;
            cin >> l >> r >> c;
            radd(l, r, c);
        } else {
            int l, r;
            cin >> l >> r;
            cout << psum(r) - psum(l - 1) << "\n";
        }
    }
    return 0;
}

复杂度分析:

  • 时间复杂度: 。初始化需要，每次操作。
  • 空间复杂度: 。用于两个树状数组。

这个技巧将差分思想的威力发挥到了极致，它告诉我们，通过巧妙的数学变形，看似复杂的操作可以被分解为若干个基础操作的组合。

第五章：超越线性 - 树上的差分艺术

前缀和与差分的思想不仅限于一维数组和二维网格，它们可以被优雅地推广到树形结构上。这在处理涉及子树或路径的批量修改时尤为重要。

核心思路是将树形结构线性化，然后应用我们已经熟悉的序列上的差分技巧。最常用的线性化方法是DFS序。

5.1 子树修改与查询

对一棵树进行深度优先搜索（DFS），我们可以记录下每个节点的两个关键时间戳：

  • ：第一次访问到节点的时间。
  • ：访问完的整个子树，即将离开的时间。

一个至关重要的性质是：节点的子树中的所有节点，它们的值都在这个区间内。

这意味着，对节点的整个子树进行操作，等价于对 DFS 序这个线性序列上的一个连续区间进行操作。

问题：支持对某个节点的子树内所有节点加上一个值，最后查询每个节点的最终值。

这正是我们熟悉的一维差分模型！

  1. 对树进行一次 DFS，求出所有节点的和，并建立一个以值为索引的线性数组。
  2. 对子树加的操作，转化为在线性数组的和。
  3. 所有修改完成后，对差分数组求前缀和，得到每个值位置上的最终增量。
  4. 再通过一个映射，将值的结果赋回给原树的节点。

题意概括:
给定一棵个节点的树，根为 1。有次操作，每次将节点及其所有子孙节点的值都加上。所有操作结束后，输出每个节点的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100005;
int n, m;
vector<int> g[N];
int in[N], out[N], t;
ll d[N]; // 差分数组, 基于DFS序
ll val[N]; // 节点最终的值

void dfs(int u, int p) {
    in[u] = ++t;
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
    out[u] = t;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0); // 预处理DFS序

    while (m--) {
        int u, c;
        cin >> u >> c;
        d[in[u]] += c;
        if (out[u] + 1 <= n) {
            d[out[u] + 1] -= c;
        }
    }

    // 在DFS序上求前缀和
    for (int i = 1; i <= n; ++i) {
        d[i] += d[i - 1];
    }

    // 将结果映射回原节点
    // 假设 id[tin] = u, 那么 val[u] = d[tin]
    // 这里我们可以直接遍历所有节点来赋值
    for (int i = 1; i <= n; ++i) {
        val[i] = d[in[i]];
        cout << val[i] << " ";
    }
    cout << "\n";

    return 0;
}

复杂度分析:

  • 时间复杂度: 。DFS 预处理，每次修改，最后还原。
  • 空间复杂度: 。

5.2 路径修改与查询

对树上两点之间的唯一简单路径进行修改，是另一个经典问题。这比子树修改要复杂一些。

同样地，我们将利用差分思想。对路径上的所有节点加，可以分解为：

  1. 对到根节点的路径加。
  2. 对到根节点的路径加。

但是这样，到根节点的路径被加了两次，需要减掉一次。并且，本身也被加了两次，但它属于路径，所以它应该只被加一次。

正确的操作是：

  1. ：让到根的路径增加。（通过后续的前缀和/子树和实现）
  2. ：让到根的路径增加。
  3. ：以上的部分被加了两次，减掉一次。
  4. ：本身被加了两次，但到根的部分已经在上一步被修正。本身的值多加了一次，需要减掉。我们通过在处减来实现。当从叶节点向根节点累加求和时，这个会抵消掉一次从传递上来的。

最终，一个节点的真实值，是它子树内所有差分值的和。

这个求和过程可以通过一次 DFS 完成。

操作流程：

  1. 预处理 LCA 相关信息（如倍增法）。
  2. 对于每次路径修改加：
    • 求出和。
    • (如果不是根)
  3. 所有修改完成后，进行一次 DFS，从叶节点向根节点累加数组的值，计算出每个节点的最终值。

题意概括:
给定一棵个节点的树和次操作。每次操作将到的路径上所有节点的值加。最后输出每个节点的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100005, LOGN = 17;
int n, m;
vector<int> g[N];
ll d[N];
int dep[N], fa[N][LOGN];

void dfs1(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u][0] = p;
    for (int i = 1; i < LOGN; ++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int v : g[u]) {
        if (v == p) continue;
        dfs1(v, u);
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LOGN - 1; i >= 0; --i) {
        if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    }
    if (u == v) return u;
    for (int i = LOGN - 1; i >= 0; --i) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

// DFS求最终值, val[u] = sum of d in subtree(u)
void dfs2(int u, int p) {
    for (int v : g[u]) {
        if (v == p) continue;
        dfs2(v, u);
        d[u] += d[v];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    dfs1(1, 0); // 预处理LCA

    while (m--) {
        int u, v, c; // 假定 c=1
        cin >> u >> v >> c;
        int l = lca(u, v);
        d[u] += c;
        d[v] += c;
        d[l] -= c;
        if (fa[l][0] != 0) d[fa[l][0]] -= c;
    }
    
    dfs2(1, 0); // 从叶到根累加差分值

    for (int i = 1; i <= n; ++i) {
        cout << d[i] << " ";
    }
    cout << "\n";

    return 0;
}

复杂度分析:

  • 时间复杂度: 。预处理 LCA ，每次修改和 LCA 查询，最后 DFS 还原。
  • 空间复杂度: 。

第六章：思想的升华 - 洞察本质

行文至此，我们已经遍历了前缀和与差分从一维到二维，从静态到动态，从线性到树形的各种应用。但技术的学习不应止于记忆公式和模板。那么背后有哪些竞赛哲学呢？

6.1 求和与求差：计算的对偶性

前缀和与差分，本质上是一对互逆的运算。在连续的世界里，这对应着微积分中的积分与微分。

  • 前缀和（Summation） 类似于 积分（Integration）：它累积了之前所有的量，得到一个总量。
  • 差分（Difference） 类似于 微分（Differentiation）：它衡量了相邻状态之间的变化率。

理解这种对偶性，能让你在遇到新问题时，自然地从两个角度思考。如果一个问题在“求和”域难以处理（例如区间修改），不妨切换到“差分”域，问题可能就迎刃而解（变为单点修改）。这种思维切换的能力十分重要。

6.2 变换：算法设计的灵魂

前缀和与差分最深刻的贡献，在于它们提供了一种变换的视角。

  • 范围 端点：将对一个范围（区间/矩形/子树/路径）的繁重操作，转化为对该范围几个关键“端点”或“拐点”的轻量操作。这是最核心的降维打击。
  • 动态 静态：将动态的修改和查询问题，通过差分数组，转化为对一个静态数组的预处理和查询。
  • 几何 线性：将树、图等复杂的几何结构，通过 DFS 序等技巧，变换为我们更擅长处理的线性序列问题。

算法竞赛的很多难题，其突破口就在于找到一个合适的变换，将一个看似棘手的问题，映射到一个我们拥有成熟解决方案的经典模型上。前缀和与差分，正是这种变换思想最朴素、最直接的体现。

6.3 常见陷阱与实践指南

  1. 下标处理：强烈建议始终使用 1-based 索引，并让前缀和数组或等于 0。这能极大简化边界条件，减少或等情况的特判，让这样的公式普适。
  2. 数据类型：切记，和的增长速度可能远超单个元素。个值为的数相加，会轻易超出 32 位整数范围。养成使用存储前缀和、差分累加值的习惯。
  3. 差分还原：在离线差分问题中，最常见的错误是忘记在所有修改操作之后，进行最后一次全局的前缀和计算来还原最终数组。差分数组本身不是答案！
  4. 二维差分的四个点：, , , ，以及它们的符号，是初学者极易混淆的地方。画图、理解容斥原理是记忆它的最好方式，而不是死记硬背。
  5. 树上差分的两种模型：要清晰地区分子树修改和路径修改所对应的不同差分模型。子树修改对应DFS序上的区间修改；路径修改对应在原树节点上标记，最后通过一次DFS自底向上累加。

写在最后

我们从最简单的出发，一路探索，最终触及了与高级数据结构和树论结合的复杂应用。你或许会发现，许多精妙算法的内核，都植根于这种朴素的思想。

很多时候，最优雅的解法，就藏在最简单的思想背后。于平凡中见神奇。

附录：例题选讲

P3128 [USACO15DEC] Max Flow P

题目描述

Farmer John 在他的谷仓中安装了条管道，用于在个牛棚之间运输牛奶（），牛棚方便地编号为。每条管道连接一对牛棚，所有牛棚通过这些管道相互连接。

FJ 正在对牛棚之间泵送牛奶（）。对于第对牛棚，你被告知两个牛棚和，这是牛奶以单位速率泵送的路径的端点。FJ 担心某些牛棚可能会因为过多的牛奶通过它们而不堪重负，因为一个牛棚可能会作为许多泵送路径的中转站。请帮助他确定通过任何一个牛棚的最大牛奶量。如果牛奶沿着从到的路径泵送，那么它将被计入端点牛棚和，以及它们之间路径上的所有牛棚。

输入格式

输入的第一行包含和。

接下来的行每行包含两个整数和（），描述连接牛棚和的管道。

接下来的行每行包含两个整数和，描述牛奶泵送路径的端点牛棚。

输出格式

输出一个整数，表示通过谷仓中任何一个牛棚的最大牛奶量。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4

输出 #1

1
9

说明/提示

。

题解

题意分析

问题的核心是，在一个树形结构上，进行次路径增值操作（每次将一条路径上所有节点的值加 1），最后求出所有节点中的最大值。这是一个典型的离线批量修改，单次查询问题，完美契合了树上差分的应用场景。

思路转换

直接对每条路径进行遍历修改的复杂度是，无法接受。我们需要利用差分思想，将一次“路径修改”转化为常数次“单点修改”。

我们已经知道，对于树上路径的修改，可以利用其最近公共祖先来进行拆解。对路径上所有点的值加，等价于对一个差分数组进行如下四个单点操作：

这里的“差分”含义是：一个节点的最终值，等于其子树内所有节点的值之和。

  • 使得从到根的路径上所有节点的值都增加了。
  • 使得从到根的路径上所有节点的值都增加了。
  • 此时，从到根的路径被加了两次，而路径上的其他节点只被加了一次。我们需要修正这个多余的增量。
  • 将及其祖先的增量修正为。
  • 但是，本身也属于路径，它应该只被加一次。经过前三步，它的值被正确地增加了。然而，的父节点（如果存在）不属于路径，却因为前两步操作也被增加了。因此，用来抵消掉对父节点及以上部分的影响。

算法流程

  1. 预处理 LCA：通过一次 DFS 预处理出每个节点的深度和父节点，然后使用倍增法构建数组，以便在时间内查询 LCA。
  2. 差分修改：遍历次操作，对于每次路径，计算，然后执行上述四次单点差分修改。
  3. 还原最终值：再次进行一次 DFS。在回溯的过程中，将子节点的值累加到父节点上，即(其中是的子节点)。DFS 结束后，就存储了节点的最终牛奶量。
  4. 寻找最大值：遍历所有节点的最终值，找到最大值并输出。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 50005, LOGN = 17;
int n, k;
vector<int> g[N];
int dep[N], fa[N][LOGN];
int d[N]; // 差分数组


void dfs1(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u][0] = p;
    for (int i = 1; i < LOGN; ++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int v : g[u]) {
        if (v == p) continue;
        dfs1(v, u);
    }
}


int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LOGN - 1; i >= 0; --i) {
        if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    }
    if (u == v) return u;
    for (int i = LOGN - 1; i >= 0; --i) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

void dfs2(int u, int p) {
    for (int v : g[u]) {
        if (v == p) continue;
        dfs2(v, u);
        d[u] += d[v]; // 从子树累加差分值
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs1(1, 0); // 预处理LCA

    for (int i = 0; i < k; ++i) {
        int u, v;
        cin >> u >> v;
        int l = lca(u, v);
        d[u]++;
        d[v]++;
        d[l]--;
        if (fa[l][0] != 0) d[fa[l][0]]--; // lca的父节点存在时才操作
    }

    dfs2(1, 0); // 还原最终值

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, d[i]);
    }
    cout << ans << "\n";

    return 0;
}

复杂度分析

  • 时间复杂度: 。预处理 LCA 占，每次路径修改查询 LCA 占，共次，最后 DFS 还原为。
  • 空间复杂度: 。主要用于存储倍增的数组。

P1438 无聊的数列

题目背景

无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的 YYB 想出了一道无聊的题：无聊的数列。。。

题目描述

维护一个数列，支持两种操作：

  • ：给出一个长度等于的等差数列，首项为，公差为，并将它对应加到范围中的每一个数上。即：令。

  • ：询问序列的第个数的值。

输入格式

第一行两个整数数表示数列长度和操作个数。

第二行个整数，第个数表示。

接下来的行，每行先输入一个整数。

若则再输入四个整数；

若则再输入一个整数。

输出格式

对于每个询问，一行一个整数表示答案。

输入输出样例 #1

输入 #1

1
2
3
4
5 2
1 2 3 4 5
1 2 4 1 2
2 3

输出 #1

1
6

说明/提示

数据规模与约定

对于数据，。

题解

这道题是差分思想应用的经典范例，但它需要的不仅仅是一次差分。之前我们探讨了使用“二阶差分”的思路来解决，虽然可行，但推导略显繁琐。

核心思想：将等差数列变换为线性函数

我们首先分析“区间加上一个首项为，公差为的等差数列”这个操作。对于区间内的任意一个位置（），它被加上了的值是：

'_' allowed only in math mode \text{value_added}(i) = K + (i - l) \times D

这是一个关于位置的表达式。让我们对它进行代数变形，整理成的形式：

'_' allowed only in math mode \text{value_added}(i) = K + i \cdot D - l \cdot D = (D) \cdot i + (K - l \cdot D)

这个变换是本题解法的灵魂。它告诉我们，给一个区间加上等差数列，等价于给这个区间内的每个点加上一个关于的线性函数，其中斜率，常数项。

分解与维护

现在，问题变成了：对区间的每个点，其值的增量为。

我们可以将这个增量分解为两部分：

  1. 斜率部分：
  2. 常数部分：

这意味着，我们可以把原问题拆解成两个独立的子问题：

  • 子问题1：对区间的每个点，其值增加。
  • 子问题2：对区间的每个点，其值增加一个常数。

子问题2是一个标准的区间加常数问题。而子问题1似乎依然棘手。

但我们换个角度看。最终查询点的值时，其总增量是所有作用于它的修改带来的增量之和。每个修改都是的形式。因此，总增量为：

其中，求和的范围是所有覆盖了点的修改操作。

这给了我们一个惊人的启示：

  • 我们只需要维护每个点被覆盖的总斜率。
  • 我们只需要维护每个点被覆盖的总常数。

而这两个维护任务，都是区间加常数，单点查询的经典模型！这个模型可以用“差分 + 树状数组”在时间内解决。

算法流程

  1. 数据结构：

    • 使用一个树状数组，来维护所有斜率的差分数组。
    • 使用另一个树状数组，来维护所有常数项的差分数组。
    • 初始数组单独存储，因为和只记录增量。

  2. **修改操作**：

    • 计算斜率和常数项。
    • 更新斜率：要对区间的总斜率加上，我们对所维护的差分数组执行。这对应到树状数组上就是和。
    • 更新常数项：要对区间的总常数项加上，我们对所维护的差分数组执行。这对应到树状数组上就是和。

  3. **查询操作**：

    • 查询总斜率：点上的总斜率就是所维护的差分数组的前缀和。这通过计算。
    • 查询总常数项：点上的总常数项就是所维护的差分数组的前缀和。这通过计算。
    • 计算最终值：根据我们的推导，点的最终值为：

    '_' allowed only in math mode a_{\text{final}}[p] = a_{\text{initial}}[p] + \text{total_C} + p \cdot \text{total_D}

    这恰好是。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct BIT {                 // 树状数组：用于维护差分数组
    vector<ll> t; int n;
    BIT(int _n=0){ init(_n); }
    void init(int _n){ n=_n; t.assign(n+1,0); }
    void add(int x,ll v){ for(;x<=n;x+=x&-x) t[x]+=v; }
    ll  sum(int x){ ll s=0; for(;x;x-=x&-x) s+=t[x]; return s; }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n,m;  cin>>n>>m;
    vector<ll> a(n+2); // 数组开大一点以防r+1越界
    for(int i=1;i<=n;i++) cin>>a[i];

    // fc维护常数项C的差分数组, fb维护斜率D的差分数组
    BIT fc(n+1), fb(n+1);

    while(m--){
        int op;  cin>>op;
        if(op==1){
            int l,r; ll k,d;  cin>>l>>r>>k>>d;
            // 增量函数为 f(i) = d*i + (k - l*d)
            // 斜率 B = d, 常数项 C = k - l*d
            ll c = k - 1LL*l*d;
            
            // 对[l,r]区间加上常数项c
            fc.add(l,  c);  fc.add(r+1,-c);
            
            // 对[l,r]区间加上斜率d
            fb.add(l,  d);  fb.add(r+1,-d);
        }else{
            int p; cin>>p;
            // a_final[p] = a_initial[p] + total_C_at_p + p * total_D_at_p
            // total_C_at_p = fc.sum(p)
            // total_D_at_p = fb.sum(p)
            ll res = a[p] + fc.sum(p) + 1LL*p*fb.sum(p);
            cout<<res<<"\n";
        }
    }
    return 0;
}

对比与总结

这种线性变换法与二阶差分法在数学上是等价的，但它提供了不同的视角：

  • 二阶差分法：是一种纯粹的、机械的“降维”操作，通过两次差分将复杂修改简化为单点修改。
  • 线性变换法：更侧重于分析增量本身的代数结构，将等差数列看作线性函数，然后分解这个函数，将问题转化为两个更简单的、我们熟知的子问题。

这种方法不仅代码简洁，而且思路的每一步都具有清晰的物理意义（斜率、常数项），更容易理解和推广。它完美地诠释了算法设计中“变换”与“分解”思想的威力。

  • Title: 前缀和与差分
  • Author: YZY
  • Created at : 2025-06-17 22:06:49
  • Updated at : 2025-06-17 22:06:49
  • Link: https://blog.dtoj.team/2025/06/17/前缀和与差分/
  • License: 三金家的Y同学
Comments
On this page
前缀和与差分
  1. 序言
  2. 第一章：一维前缀和
    1. 1.1 定义与核心思想
    2. 1.2 核心操作：区间查询
    3. 1.3 代码实现与典型应用
  • 第二章：一维差分 - 静态世界的动态修改
    1. 2.1 定义与核心思想
    2. 2.2 核心操作：区间修改
    3. 2.3 从差分到原数组
    4. 2.4 代码实现与典型应用
  • 第三章：二维世界的延伸
    1. 3.1 二维前缀和
    2. 3.2 二维差分
  • 第四章：动态世界 - 与数据结构的联系
    1. 4.1 前缀和与树状数组：天作之合
    2. 4.2 差分与树状数组：优雅的降维打击
    3. 4.3 双树状数组下的区间修改与区间查询
  • 第五章：超越线性 - 树上的差分艺术
    1. 5.1 子树修改与查询
    2. 5.2 路径修改与查询
  • 第六章：思想的升华 - 洞察本质
    1. 6.1 求和与求差：计算的对偶性
    2. 6.2 变换：算法设计的灵魂
    3. 6.3 常见陷阱与实践指南
  • 写在最后
  • 附录：例题选讲
  • P3128 [USACO15DEC] Max Flow P
  • P1438 无聊的数列