[算法学习]模板-一维前缀和 & 一维差分

一维前缀和与一维差分是竞赛中最基础、最重要的两个数组技巧。

它们本质互为逆运算：

差分 = 前缀和的逆运算
前缀和 = 差分的还原操作

---

一、一维前缀和

核心思想：空间换时间

用于解决：

多次区间求和问题

暴力查询区间 [l, r]：

for i in [l, r]:
    sum += a[i]

时间复杂度：

O(n × q)

前缀和优化后：

O(n + q)

---

1. 原理剖析

设原数组：

a[1], a[2], ..., a[n]

定义前缀和数组：

prefix[i] = a[1] + a[2] + ... + a[i]

区间和公式：

sum(l, r) = prefix[r] - prefix[l - 1]

推导

prefix[r] = a[1] + ... + a[l-1] + ... + a[r]
prefix[l-1] = a[1] + ... + a[l-1]

相减后：

a[l] + ... + a[r]

---

2. 模板代码

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

const int N = 1e6 + 10;

ll prefix[N];

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

    int n, q;
    cin >> n >> q;

    // 构建前缀和
    for(int i = 1; i <= n; i++)
    {
        cin >> prefix[i];
        prefix[i] += prefix[i - 1];
    }

    // 区间查询
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << '\n';
    }

    return 0;
}

---

3. 关键细节

① 下标从 1 开始

保证：

prefix[0] = 0

当 l = 1 时不会越界。

---

② 使用 long long

若：

n = 1e6
a[i] = 1e9

前缀和可能达到：

1e15

必须使用 long long。

---

③ 时间复杂度

阶段	复杂度
预处理	O(n)
单次查询	O(1)
总复杂度	O(n + q)

---

二、一维差分

核心思想：区间修改转化为单点操作

用于解决：

多次区间加法修改问题

暴力修改：

for i in [l, r]:
    a[i] += d

时间复杂度：

O(n × q)

差分优化后：

O(n + q)

---

1. 原理剖析

设原数组：

a[1], a[2], ..., a[n]

定义差分数组：

b[i] = a[i] - a[i - 1]

则：

a[i] = b[1] + b[2] + ... + b[i]

---

区间加法实现

若要：

a[l..r] 每个数 + d

只需：

b[l] += d
b[r+1] -= d

最后对 b 做前缀和即可还原。

---

2. 模板代码

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

const int N = 1e6 + 10;

ll a[N];
ll b[N];

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

    int n, q;
    cin >> n >> q;

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

    // 区间修改
    while(q--)
    {
        int l, r;
        ll d;
        cin >> l >> r >> d;

        b[l] += d;
        b[r + 1] -= d;
    }

    // 还原数组
    for(int i = 1; i <= n; i++)
    {
        b[i] += b[i - 1];
        cout << b[i] << " ";
    }

    return 0;
}

---

3. 关键细节

① r+1 是否越界？

数组大小为：

N = 1e6 + 10

访问 b[n+1] 安全。

---

② 为什么最后要前缀和？

因为：

a[i] = b[1] + ... + b[i]

差分数组本身不是最终结果。

---

③ 时间复杂度

阶段	复杂度
构造差分	O(n)
每次修改	O(1)
还原数组	O(n)
总复杂度	O(n + q)

---

三、前缀和与差分对比

技术	解决问题
前缀和	区间查询
差分	区间修改

记忆方式：

查询用前缀和
修改用差分

---

四、总结

一维前缀和与一维差分是所有区间类数据结构的基础。

后续进阶方向：

• 二维前缀和
• 二维差分
• 树状数组
• 线段树

掌握这两个模板，是学习高级数据结构的前置条件。