• C++
  • 前缀和 + 差分 C++ 教程(GESP五级)

  • @ 2026-10-21 23:07:11

前缀和 + 差分 C++ 教程(GESP五级)

前置:数组、循环 核心定位:快速求一段区间的和、快速给一段区间统一加减数字 重点:数学原理、什么时候用、为什么比循环快、代码、背诵口诀、坑点


一、前缀和

1. 数学道理

原数组 a[1],a[2],a[3]...a[n] 前缀和数组 s,规定:

s[0]=0s[0] = 0 s[i]=a[1]+a[2]+a[3]+...+a[i]s[i] = a[1]+a[2]+a[3]+...+a[i]

👉 s[i]:前 i 个数全部加起来的总和

区间求和公式(最重要!) 求从 l 到 r 这个区间所有数字的和:

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

举例子: a = [0, 5, 2, 7, 1] (下标从1开始) (s[0] = 0) s[1]=5 s[2]=5+2=7 s[3]=5+2+7=14 s[4]=5+2+7+1=15

求 l=2,r=3(a[2]+a[3] = 2+7=9) s[3]-s[1] = 14 - 5 = 9 ✔

✅ 优势: 普通做法:每次查询区间和,for循环一遍 l~r。如果查询很多次,很慢。 前缀和:先花一次时间预处理s数组,之后每一次区间求和,只需要一次减法 O(1)

一句话:预处理一次,查询随便秒算。

2. 前缀和完整代码,逐行注释

#include <iostream>
using namespace std;
const int N = 100010; // 数组最大长度
int a[N], s[N];        // a原数组,s前缀和数组

int main()
{
    int n, q;
    cin >> n >> q; // n数字个数,q次查询
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

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

    // 处理q次区间查询
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl;
    }
    return 0;
}

📖 背诵口诀(前缀和)

  1. 下标从1开始,(s[0] = 0)
  2. s[i] = s[i-1] + a[i]
  3. 区间 l~r 和:s[r] - s[l-1]

⚠️ 大坑:l不能写成 s[l],一定是 l-1!


二、差分(差分数组)

1. 数学道理(配合前缀和理解)

差分是前缀和的逆操作! 需求:给区间 [l, r] 里面每一个数都加上一个数 d 如果直接循环 l~r 一个个加,区间很大、修改次数很多的时候很慢。

差分数组 b: 性质:b数组的前缀和,就是原数组a。

差分修改公式:

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

修改全部做完之后,对b求一遍前缀和,就得到修改后的a数组!

举例: 原数组 a:[0, 1,2,3,4] b初始全0 我们要:l=2,r=3,全部 +5

b[2] +=5
b[4] -=5

之后求b的前缀和: b前缀:0,5,5,0 得到 a:1, 2+5,3+5,4 ✔ 只有2、3位置加上了5,完美。

✅ 优势: 一次区间加操作,只改两个位置 O(1)。 所有修改做完,最后只跑一遍前缀和还原数组。

一句话记忆差分:一加一减,最后跑前缀和还原。

2. 差分完整代码,逐行注释

#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N]; // a原数组,b差分数组

// 差分插入函数:给[l,r]加上d
void insert(int l, int r, int d)
{
    b[l] += d;
    b[r+1] -= d;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        insert(i, i, a[i]); // 初始化差分:相当于a[i]放到b
    }

    // m次区间修改:l r d
    while(m--)
    {
        int l, r, d;
        cin >> l >> r >> d;
        insert(l, r, d);
    }

    // 对差分数组求前缀和,得到修改后的数组
    for(int i = 1; i <= n; i++)
    {
        b[i] = b[i-1] + b[i];
        cout << b[i] << " ";
    }
    return 0;
}

📖 背诵口诀(差分)

  1. 差分核心函数:b[l]+=d; b[r+1]-=d;
  2. 所有修改做完,对b跑前缀和
  3. 结果就是修改完成的数组

⚠️ 大坑:r+1 不能越界!r等于n的时候,r+1是n+1,数组要开大一点。


三、前缀和 vs 差分对比(板书)

算法 擅长干什么 操作 流程
前缀和 多次查询【区间求和】 预处理一次前缀和,查询减法 先预处理,再查询
差分 多次【区间统一加/减】,最后看数组 每次修改只改两点,最后前缀和还原 先全部修改,最后还原

区分一句话: 问区间总和 → 前缀和 给一段区间集体加数字 → 差分

四、极简手动模拟(n=4)

a = [1,2,3,4] 差分b初始0 操作:l=2 r=3 d=+5 b[2]+=5,b[4]-=5 b数组:[0,0,5,0,-5] 求前缀和: i=1:0 →1 i=2:0+5=5 →2+5 i=3:5+0=5 →3+5 i=4:5-5=0 →4

五、配套课堂小练习

  1. 前缀和:a=[3,1,4,2], 求 l=2,r=4 的和
  2. 差分:数组 [10,20,30,40],执行 l=1,r=3 全部+2,写出b数组变化和最终数组

答案

  1. s[4]-s[1] = (3+1+4+2)-3 = 7
  2. b[1]+=2,b[4]-=2;最终:12,22,32,40

六、拓展提醒(GESP考点)

前缀和、差分默认下标从1开始,避开0的麻烦,是竞赛约定写法。 二维前缀和、二维差分是进阶,五级先吃透一维。

0 条评论

目前还没有评论...