『学习笔记』前缀和与差分

· · 个人记录

今天我在 \texttt{OI-Wiki} 艰难地学废了前缀和与差分，其设计十分精妙，用于序列中进行各种操作的场景，例如区间加法、减法，求出区间和等等。

为方便表示，定义左上角为 (x_1,y_1)，右下角为 (x_2,y_2) 的矩阵为 (x_1,y_1),(x_2,y_2)。

前缀和

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前 n 项的和”。 ——\texttt{OI-Wiki}

一维前缀和

定义一个数组 a：[1,2,3,4,5]。

构造

我们要建立一个前缀和数组 sum，sum_n=\sum\limits_{i=1}^{n}a_i，也就是 sum_n 等于数组 a 前 n 项的和。

由此我们可以得到构造 sum 的公式：

sum_i= \begin{cases} a_1 & i=1\\ sum_{i-1}+a_i & i \ne 1 \end{cases}

由于在 C++ 中，数组开在全局时默认全部为 0，我们从 a_1 开始用，所以不用管边界问题。当 i=1 时，sum_{i-1=0}=0，sum_{i-1}+a_i 也就等于 a_i。

我们可以一边读入一边建立数组，像这样：

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

那么可得前缀和数组 sum：[1,3,6,10,15]。

区间查询

假设要查询区间 [l,r] 的和。

可以由 sum_r 就是区间 [1,r] 的和，sum_l 就是区间 [1,l] 的和想到利用 sum_r 和 sum_{l-1} 这两个数。因为区间 [1,r] 减去 [1,l-1] 就只剩 [l,r] 的和了。

cout << sum[r]-sum[l-1] << endl;

可见前缀和也是很简单的。

例题

U53525 前缀和（例题）

这题就和上面的栗子一模一样，输入 n 和数组 a，直接输出前缀和数组 sum 即可。

#include <iostream>
using namespace std;
template<typename T=int>
inline T read(){
    T X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

template<typename T=int>
inline void write(T X){
    if(X<0) putchar('-'),X=~(X-1);
    T s[20],top=0;
    while(X) s[++top]=X%10,X/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    putchar('\n');
}
int n,a[105],sum[105];

int main(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        sum[i]=sum[i-1]+a[i];
        cout << sum[i] << " ";
    }
    puts("");
    return 0;
}

但可以进行空间优化，使用滚动数组，因为每次只需用到 sum_i 和 sum_{i-1} 所以可以用 a 和 b 两个变量代替，原先的 a 数组也不需要，直接输入 b 即可。

#include <iostream>
using namespace std;
template<typename T=int>
inline T read(){
    T X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

template<typename T=int>
inline void write(T X){
    if(X<0) putchar('-'),X=~(X-1);
    T s[20],top=0;
    while(X) s[++top]=X%10,X/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    putchar('\n');
}

int main(){
    int n,a=0,b=0;
    cin >> n;
    while(n--){
        cin >> b;
        b+=a;
        cout << b << " ";
        a=b;
    }
    return 0;
}

P1115 最大子段和

上面两道题就是构造数组，这道相对综合一点。

给定一个长度为 n 的序列 a，求出最大连续子段和。

由于要求的是连续子段和，很容易想到递推。也可以说是选择性的前缀和。

老样子，滚动数组，只不过滚动的是前缀和数组，代码中的 a 只是输入用的，b 是滚动数组的前一项，c 是当前这一项的前缀和。

至于 c \gets \max{\{b+a,a\}}，也很容易理解。b 是题目中的数组前一项的前缀和，若这一项的前缀和比前一项还小，那么当前的数作为当前前缀和就是最优方案。更新答案就不用多说了吧。

代码：

#include <iostream>
using namespace std;
template<typename T=int>
inline T read(){
    T X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

template<typename T=int>
inline void write(T X){
    if(X<0) putchar('-'),X=~(X-1);
    T s[20],top=0;
    while(X) s[++top]=X%10,X/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    putchar('\n');
}
int n,a,b,c,ans=-0x7fffffff;

int main(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a;
        c=max(b+a,a);
        ans=max(c,ans);
        b=c;
    }
    cout << ans << endl;
    return 0;
}

习题

二维前缀和

我们看 a 数组：

\begin{matrix}& \begin{matrix} 1&2&3\\ \end{matrix}\\ \begin{matrix} 1\\2\\3\\ \end{matrix}& \begin{bmatrix} 1&2&3\\ 4&5&6\\ 7&8&9\\ \end{bmatrix} \end{matrix}

设 sum_{x,y}=\sum\limits^x_{i=1}\sum\limits^y_{j=1}a_{i,j}，那么 sum 数组：

\begin{matrix}& \begin{matrix} 1&2&3\\ \end{matrix}\\ \begin{matrix} 1\\2\\3\\ \end{matrix}& \begin{bmatrix} 1&3&6\\ 5&12&21\\ 12&27&45\\ \end{bmatrix} \end{matrix}

构造

现在的第一个问题是如何建立这个数组。

图中应该说得很清楚了，于是我们得到公式：sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j}。

区间查询

如何截取一个矩形？也很简单。

设要截取的矩形的长为 x，宽为 y：

可以发现，这和上面的构造差不多。查询公式(设要求矩阵为 (x_1,y_1),(x_2,y_2))：

\sum\limits^{x}_{u=i}\sum\limits^{y}_{v=y_1}=sum_{i+x,j+y}-sum_{i-1,j+y}-sum_{i+x,j-1}+sum_{i-1,j-1}

例题

U184421 退钱

是的，你没看错。这就是我那道 WFOI 被毙掉的题(真的好垃)。

有一个 n \times n 的矩阵 a，给定 q 次询问，每次询问给出子矩阵坐标 (x_1,y_1,x_2,y_2)，若：

怎么样，跟板子没区别吧？

官方题解，应该还可以吧？

P1387 最大正方形

我们要在 n \times m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形，输出边长。

这题数据范围很小，1\le{n,m}\le100 矩阵的值只包含 0 和 1，虽说可以使用 bool 但是这些我推荐使用 int，除非你怕爆栈。

首先构造前缀和数组，不用多说，直接套：sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j} 。

两层循环，i 从 1 到 n-1，j 从 1 到 m-1。

题目要求输出正方形，再套一层循环，变量 l 枚举 1~\min(n-i,m-i)，因为最大的边长等于 n-i 和 m-i 中最小的那个。

每次判断：sum_{i+l,j+l}-sum_{i+l,j}-sum_{i,j+l}+sum_{i,j}==l \times l，l \times l 就是这个矩形的面积，如果和等于面积，那么就能确定这个矩形全部为1，更新 ans：ans=\max(ans,l)。

代码：

#include <iostream>
using namespace std;
template<typename T=int>
inline T read(){
    T X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

template<typename T=int>
inline void write(T X){
    if(X<0) putchar('-'),X=~(X-1);
    T s[20],top=0;
    while(X) s[++top]=X%10,X/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    putchar('\n');
}
int n,m,a[105][105],sum[105][105],ans;

int main(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    }
    for(int i=1; i<n; i++){
        for(int j=1; j<m; j++){
            for(int l=1,t=min(n-i,m-j); l<=t; l++){
                if(sum[i+l][j+l]-sum[i+l][j]-sum[i][j+l]+sum[i][j]==l*l){
                    ans=max(ans,l);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

习题

差分

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

——OI-Wiki

上面提到过差分，差分是前缀和的逆运算，也就是将一个前缀和数组转换成原数组。

一维差分

差分可以用来解决区间加法之类的问题，但中间如果要修改就不太适合了。

一般情况下，使用差分，会将原数组看作一个前缀和数组，然后将每一项差分成这个前缀和数组的原数组，递推式为：dif_i=a_i-a_{i-1}(a_0=0) 其中 dif 表示差分数组。

如何修改呢？我们可以分析一下原数组改动对前缀和数组的影响（dif 为原数组，a 为前缀和数组）：如果 dif_i \gets dif_i+k，那么 a_{[i,n]} 均会加上 k。

这式修改 a_{[i,n]} 的方法，修改 [l,r] 的方法也很容易推理出来：先将 dif_l 加上 k，就是将 a_{[l,n]} 都加上了 k。你会发现 a_{[r+1,n]} 这个区间也加上了 k，这时只需将 dif_{r+1} 加上 k 即可。

构造差分数组：

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

区间加（将区间 [l,r] 加上 k）：

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

最后求原数组时，只需对 dif 进行一次前缀和操作，即可得到修改后的原数组。

通过这些精妙的计算，可以快速地实现区间加法，并在最后使用 \mathcal{O}(n) 的时间复杂度得出最终数组。

例题

U69096 前缀和的逆

读入前缀和数组 sum，让你求原数组 a，我们只需每次读入后减去上一个就行了：a_i=sum_i-sum_{i-1}。

正常爆栈数组版代码：

#include <iostream>
using namespace std;
template<typename T=int>
inline T read(){
    T X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

template<typename T=int>
inline void write(T X){
    if(X<0) putchar('-'),X=~(X-1);
    T s[20],top=0;
    while(X) s[++top]=X%10,X/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    putchar('\n');
}
int n,a[105],sum[105];

int main(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> sum[i];
        a[i]=sum[i]-sum[i-1];
        cout << a[i] << " ";
    }
    puts("");
    return 0;
}

滚动数组版代码：

#include <iostream>
using namespace std;
template<typename T=int>
inline T read(){
    T X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

template<typename T=int>
inline void write(T X){
    if(X<0) putchar('-'),X=~(X-1);
    T s[20],top=0;
    while(X) s[++top]=X%10,X/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    putchar('\n');
}
int n,a,b;

int main(){
    cin >> n;
    while(n--){
        cin >> b;
        int t=a;
        a=b;
        b-=t;
        cout << b << " ";
    }
    return 0;
}

这一题是建立差分数组的题。

话说明明到底男的还是女的？

P2367 语文成绩

题目大意：有一个长度为 n 的序列 a，p 次操作，每次操作给出三个数 x,y,z，代表给区间 a_{[x,y]} 加上 k。问：最终的最小值是多少？

很简单，对原数列进行差分，每次操作区间加，最后进行前缀和操作，可以一边进行前缀和一边找最小值，具体见代码。

#include <iostream>
using namespace std;
template<typename T=int>
inline T read(){
    T X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

template<typename T=int>
inline void write(T X){
    if(X<0) putchar('-'),X=~(X-1);
    T s[20],top=0;
    while(X) s[++top]=X%10,X/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    putchar('\n');
}
int n,p,a[5000005],dif[5000005],ans=0xfffffff;

int main(){
    cin >> n >> p;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        dif[i]=a[i]-a[i-1]; // 构造差分数组
    }
    while(p--){
        int x,y,z;
        cin >> x >> y >> z;
        dif[x]+=z,dif[y+1]-=z; // 实现区间加
    }
    for(int i=1; i<=n; i++){
        a[i]=a[i-1]+dif[i]; // 对dif进行前缀和操作，得到原数组
        ans=min(ans,a[i]); // 在前缀和的同时，可以直接统计答案
    }
    cout << ans << endl;
    return 0;
}

习题

二维差分

就是二维矩阵上进行差分，和前缀和很像。

我们定义一个原矩阵 a，构造出矩阵 dif，使得 a_{i,j}=\sum\limits^{i}_{x=1}\sum\limits^{j}_{y=1}dif_{x,y}，那么 a 就是 dif 的前缀和矩阵，dif 是 a 的差分矩阵。a_{i,j} 也就是 dif 中左上角为 (1,1)，右下角为 (i,j) 的子矩阵之和。

构造

构造就先看图就行了：

如果不太懂的话可以看下面的区间修改，和构造非常像。

区间修改

若将 dif_{i,j} 进行修改，那么对 dif 进行前缀和后，(i,j),(n,m) (其中 n 为 dif 的行数，m 为 dif 的列数) 这个矩阵就都会被修改。

设要修改的矩阵为 (x_1,y_1),(x_2,y_2)，可以先将 dif_{x_1,y_1} 修改，这样矩阵 (x_1,y_1),(n,m) 就都被修改了。这里和构造非常像，只是将构造中的 i 替换为 x_1，j 替换为 y_1，i+1 替换为 x_2，j+1 替换为 y_2。

然而，矩阵 (x_2+2,y_1),(n,m) 和矩阵 (x_1,y_2+1),(n,m) 却多修改了。我们只需将 dif_{x_2+1,y_1} 和 dif_{x_1,y_2+1} 修改一下即可，但这里修改和上面的相反，例如，上面是 dif_{x_1,y_1} \gets dif_{x_1,y_1}+k，那么这里就是 dif_{x_2+1,y_1} \gets dif_{x_2+1,y_1}-k 和 dif_{x_1,y_2+1} \gets dif_{x_1,y_2+1}-k。

最后，还有一个问题，就是矩阵 (x_2+1,y_2+1),(n,m) 多减了一次，所以将 dif_{x_2+1,y_2+1} 进行正面修改即可。

代码：

dif[x1][y1]+=c;
dif[x2+1][y1]-=c;
dif[x1][y2+1]-=c;
dif[x2+2][y2+1]+=c;

单点查询

只需对 dif 数组跑一遍前缀和，再取前缀和数组里的值即可。

代码：

for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        a[i][j]=b[i][j]+a[i][j-1]+a[i-1][j]-a[i-1][j-1];
    }
}

习题

# 说句闲话：研究前缀和与差分的最好方法是 ~~A 了这**吨**题~~ ~~祝你们成功（滑稽~~ 有些数据结构会用到差分思想，例如树状数组等。但是二维差分就用的不多了。而差分可以说是基于前缀和的，所以这个算法要熟练掌握。