前缀和与差分数组

一、前缀和

1. 适用场景

前缀和主要解决：

多次查询数组某个区间的元素之和。

设原数组为：

下标：  1  2  3  4  5
a[i]： 2  1  3  4  2

定义前缀和数组：

s[i] = a[1] + a[2] + ... + a[i];

因此：

s[1] = 2
s[2] = 2 + 1 = 3
s[3] = 2 + 1 + 3 = 6
s[4] = 2 + 1 + 3 + 4 = 10
s[5] = 2 + 1 + 3 + 4 + 2 = 12

2. 构造公式

s[i] = s[i - 1] + a[i];

通常令：

s[0] = 0;

全局数组会自动初始化为 0。

3. 区间查询公式

查询区间 [l,r] 的元素之和：

sum(l, r) = s[r] - s[l - 1];

原理：

s[r]     = a[1] + ... + a[l-1] + a[l] + ... + a[r]
s[l - 1] = a[1] + ... + a[l-1]
相减后    = a[l] + ... + a[r]

4. “统计 1 的个数”问题

如果要统计区间内数字 1 出现的次数，可以定义：

s[i] = 前 i 个数字中 1 的数量

构造方式：

s[i] = s[i - 1] + (a[i] == 1);

其中：

• a[i] == 1 成立时，表达式值为 1
• a[i] == 1 不成立时，表达式值为 0

查询 [l,r] 中 1 的数量：

s[r] - s[l - 1]

5. 前缀和模板

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

using int64 = long long;

const int N = 1000000 + 10;

int n, q;
int64 a[N], s[N];

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

    cin >> n;

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

    cin >> q;

    while (q--) {
        int l, r;
        cin >> l >> r;

        cout << s[r] - s[l - 1] << '\n';
    }

    return 0;
}

6. 时间复杂度

操作	时间复杂度
构造前缀和	O(n)
单次区间查询	O(1)
q 次区间查询	O(q)
总时间复杂度	O(n+q)

---

二、差分数组

1. 适用场景

差分数组主要解决：

多次对数组的某个区间统一加上或减去一个数。

例如，执行多次操作：

将区间 [l,r] 中的所有元素都加上 k

如果逐个修改区间中的元素，单次操作最坏需要 O(n)。

使用差分数组后，单次区间修改只需要 O(1)。

2. 差分数组的定义

对于原数组 a，定义差分数组 c：

c[i] = a[i] - a[i - 1];

规定：

a[0] = 0;

因此：

c[1] = a[1]
c[2] = a[2] - a[1]
c[3] = a[3] - a[2]
...

例如：

a：1  2  3  4  5
c：1  1  1  1  1

计算过程：

c[1] = 1
c[2] = 2 - 1 = 1
c[3] = 3 - 2 = 1
c[4] = 4 - 3 = 1
c[5] = 5 - 4 = 1

3. 差分数组还原原数组

对差分数组求一次前缀和，即可得到原数组：

a[i] = a[i - 1] + c[i];

也可以直接写成：

c[i] += c[i - 1];

操作完成后，c[i] 就表示最终的 a[i]。

原理：

c[1]                         = a[1]
c[1] + c[2]                  = a[2]
c[1] + c[2] + c[3]           = a[3]
...
c[1] + c[2] + ... + c[i]     = a[i]

4. 区间修改

要让原数组的区间 [l,r] 中所有元素都加上 k：

c[l] += k;
c[r + 1] -= k;

含义：

• 从下标 l 开始，所有元素增加 k
• 从下标 r+1 开始，撤销这个增加量
• 所以只有 [l,r] 会增加 k

5. 操作示例

原数组：

a：1  2  3  4  5

执行：

将区间 [2,4] 中的元素全部加 3

结果应为：

a：1  5  6  7  5

原差分数组：

c：1  1  1  1  1  0

修改差分数组：

c[2] += 3;
c[5] -= 3;

修改后：

c：1  4  1  1  -2  0

再求一次前缀和：

1
1 + 4             = 5
1 + 4 + 1         = 6
1 + 4 + 1 + 1     = 7
1 + 4 + 1 + 1 - 2 = 5

成功还原为：

1  5  6  7  5

6. 差分数组模板

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

using int64 = long long;

const int N = 1000000 + 10;

int n, q;
int64 a[N], c[N];

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

    cin >> n;

    // 输入原数组，并构造差分数组
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        c[i] = a[i] - a[i - 1];
    }

    cin >> q;

    // 进行 q 次区间修改
    while (q--) {
        int l, r;
        int64 k;

        cin >> l >> r >> k;

        c[l] += k;
        c[r + 1] -= k;
    }

    // 对差分数组求前缀和，得到最终数组
    for (int i = 1; i <= n; i++) {
        c[i] += c[i - 1];
        cout << c[i] << (i == n ? '\n' : ' ');
    }

    return 0;
}

7. 时间复杂度

操作	时间复杂度
构造差分数组	O(n)
单次区间修改	O(1)
q 次区间修改	O(q)
还原最终数组	O(n)
总时间复杂度	O(n+q)

---

三、前缀和与差分的关系

前缀和与差分互为逆运算：

原数组 --做差--> 差分数组
差分数组 --求前缀和--> 原数组

知识点	主要用途	核心公式
前缀和	快速进行区间查询	s[i]=s[i-1]+a[i]
区间查询	查询 [l,r] 的和	s[r]-s[l-1]
差分	快速进行区间修改	c[i]=a[i]-a[i-1]
区间修改	[l,r] 全部加 k	c[l]+=k, c[r+1]-=k
数组还原	由差分数组得到原数组	c[i]+=c[i-1]

---

四、解题步骤总结

前缀和题目

1. 输入原数组。
2. 构造前缀和数组：

s[i] = s[i - 1] + a[i];

3. 查询区间 [l,r]：

s[r] - s[l - 1];

差分题目

1. 输入原数组。
2. 构造差分数组：

c[i] = a[i] - a[i - 1];

3. 对每次区间修改 [l,r] 加 k：

c[l] += k;
c[r + 1] -= k;

4. 对差分数组求前缀和：

c[i] += c[i - 1];

5. 输出最终数组或统计答案。

---

五、常见错误

1. 下标从 1 开始

推荐使用：

for (int i = 1; i <= n; i++)

这样区间公式可以直接写成：

s[r] - s[l - 1]

2. 数组需要多开一个位置

差分操作会访问：

c[r + 1]

当 r=n 时会访问 c[n+1]，因此数组长度至少要开到 n+2。

3. 数据范围较大时使用 long long

即使每个 a[i] 都能用 int 保存，前缀和也可能超过 int 范围。

推荐：

using int64 = long long;

不建议使用：

#define int long long

宏会替换代码中的所有 int，可能造成类型混乱。使用明确的类型别名更加安全。

4. 大量输出不要使用 endl

cout << answer << '\n';

通常比下面的写法更快：

cout << answer << endl;

因为 endl 每次都会强制刷新输出缓冲区。

---

六、核心口诀

区间查询，用前缀和：
前面累加，区间相减。

区间修改，用差分：
左端加上，右端后一位减去。

差分还原很简单：
从左到右再做一次前缀和。