算法笔记：前缀和 & 差分

Freezing_Winter · 2025-09-13 18:53:37 · 算法·理论

前缀和

适用范围：区间求和。

一维

例 有一个长度为 n 的数列 a，有 q 次询问，每次询问 l，r，要求输出 \sum\limits_{i=l}^{r}a_i。

首先考虑暴力，每次询问时：

int s=0;
for(int i=l;i<=r;i++)s+=a[i];
cout<<s<<'\n';

时间复杂度分析：最劣时，每次都 l=1,r=n，则时间复杂度为 O(nq)。

那么我们怎么优化呢？

我们可以再考虑一个数组 s 存储 a 的前缀和，即

稍作变形便可得出递推式：

那么这样有什么用呢？

注意到，\sum\limits_{i=l}^ra_i=\sum\limits_{i=1}^ra_i-\sum\limits_{i=1}^{l-1}a_i=s_r-s_{l-1}，这样便将 O(n) 的遍历变成了 O(1) 的计算，总复杂度直接降为 O(n+q)。

::::info[例 参考代码]

#include<bits/stdc++.h>
#define int long long
#define N 10000005//本处以n<=1e7举例 
using namespace std;
int a[N],s[N],n,q;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];}
    while(q--){
        int l,r;cin>>l>>r;
        cout<<s[r]-s[l-1]<<'\n';
    }
    return 0;
}

::::

二维

例 有一个 n 行 m 列的二维数组 a，有 q 次询问，每次询问 x_1,y_1,x_2,y_2，求 \sum\limits_{i=x_1}^{x_2}\sum\limits_{j=y_1}^{y_2}a_{i,j}。

本题与上一例极为类似，只是改成了二维。

先考虑暴力，每次 O(nm) 的遍历数组，总时间复杂度 O(qmn)。

类似地，设 s_{i,j}=\sum\limits_{k=1}^i\sum\limits_{l=1}^ja_{k,l}，易得递推式为：

可以参考图来理解（绿色部分为黄蓝的重叠处）：

预处理好 s 后，每次询问时，类似预处理的推导，易得：

复杂度优化至 O(nm+q)。

差分

适用范围：区间整体加减。

一维

例 有一个长度为 n 的数列 a，有 q 次操作，每次输入 l，r，w，要求对于每一个 i\in[l,r]，都将 a_i 的值加上 w，最后输出 a。

暴力做法为 O(nq)，可以使用差分进行优化。

定义差分数组 d，其中

为什么要把差分和前缀和放在一起呢？

我们对差分数组求前缀和，设其为 p：

于是我们得到一个重要的结论：差分数组的前缀和数组为原数组。

类似的，还可以得到：前缀和数组的差分数组为原数组。

所以：前缀和和差分互为逆运算。

回到例题，对于一次操作，设操作后的原数组和差分数组分别为 a^\prime 和 b^\prime。

分类讨论：

• 对于任意的 i\in[l+1,r]，d^\prime_i=a^\prime_i-a^\prime_{i-1}=(a_i+w)-(a_{i-1}+w)=d_i。
• 对于 i=l，d^\prime_i=(a_i+w)-a_{i-1}=d_i+w。
• 对于 i=r+1，d^\prime_i=a_i-(a_{i-1}+w)=d_i-w。

综上所述，对于 [l,r] 的区间整体加 w 的修改，仅需对差分数组 d 进行如下修改：

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