首页 > 其他 > 详细

【学习笔记】前缀和与差分

时间:2020-03-16 09:32:10      阅读:95      评论:0      收藏:0      [点我收藏+]

感谢@HsKr 纠正了版式上的一些问题QWQ。

区间问题中,若只涉及区间加/区间求和,那么可以用前缀和与差分高效的完成。


前缀和

例题:给定一个长度为 \(n\) 的序列 \(a\) ,给出 \(m\) 次操作,每次操作询问一段区间 \([l,r]\) 的值。

暴力当然可以做,但是可以利用前缀和 \(\mathcal{O}(1)\) 查询!

设 pre[i] 表示 1~i 的和,那么这个 pre 数组可以递推出来。代码大概长成这样:

for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    pre[i]=pre[i-1]+a[i]; //1~i-1的和加上当前数字就是1~i的和
}

如果仍感到难以理解可以结合下面这个表:

a:   1 2 3 4  5  6  7  8  9
pre: 1 3 6 10 15 21 28 36 45

现在我们手里有了 pre 数组,我们可以拿她做什么事呢?

如果我们需要查询 \([l,r]\) 的和,那么我们可以直接 pre[r]-pre[l-1] 。

道理呢?

放个图:

技术分享图片

红色的那部分就是 pre[r] ,即 \([1,r]\) 的和

技术分享图片

然后我们把 \([1,r]\) 的和减去 \([1,l-1]\) 的和(即蓝色的部分),得到的就是 [l,r] 的和了!

然后很多人会有一个疑问:为什么减去的不是 pre[l] 而是 pre[l-1] 呢?的确,从图上看的不是很清楚,那么请回顾 pre 数组的定义:

设 pre[i] 表示 1~i 的和

1~i 的和,也就是说,pre[l] 的值是加上了 a[l] 的 ,那么如果减去 pre[l] ,也就同时减去了 a[l] ,计算的就是 \([l+1,r]\) 的和了!(理解这一点很重要,待会差分的时候也会遇到同样的问题)。

二维前缀和

二维前缀和用于维护矩形面积。

例题:洛谷P2280、HNOI2003激光炸弹

题目意思就是说维护一个面积为 \(5001\times 5001\) 的矩形,\(n\) 个点 \((x_i,y_i)\) 会有一个权值,要求找出一个边长为 \(R\) 的正方形,使得这个正方形里所有点的权值之和最大。

\(sum_{x,y}\) 为面积为 \(x\times y\) 的矩形内所有权值之和,那么我们也可以快速递推出来(其实并不快==)

for(int i = 1; i <= n; i++)
{
    int x, y, v;
    cin >> x >> y >> v;
    sum[x + 1][y + 1] += v;
}
//DEBUG;
for(int i = 1; i <= 5001; i++)
    for(int j = 1; j <= 5001; j++)
        sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];

注意上面现把 \(sum_{x,y}\) 当作一个点来计算,然后在下一个循环时直接拿 \(sum_{x,y}\) 当作 \(a_{x,y}\) 的大小递推。由于题目中 \(x,y\) 可能等于 0,所以在实际计算时要整体下移

什么意思呢?看图理解:

技术分享图片

如图所示,我们现在要利用 \(sum_{x,y}\) 得到我们想要的这个矩形的值,那么这个值可以怎样拼凑呢?

技术分享图片

首先就是 \(sum_{x,y-1}\)

技术分享图片

然后是 \(sum_{x-1,y}\)

别忘了加上本身的权值 \(sum_{x,y}\) !(注意,此时 \(sum_{x,y}\) 未被更新,保存的仍相当于 \(a_{x,y}\) 但是之前的 sum 值都是更新过的,可以直接拿来用)。

对了么?

其实还不对,观察我们加上的区域:

技术分享图片

发现绿色部分,即 \(sum_{x-1,y-1}\) 被重复加了两次!好办,减去即可。完整的递推式就是:

\[ sum_{x,y}=sum_{x,y-1}+sum_{x-1,y}+sum_{x,y}-sum_{x-1,y-1} \]

现在我们手握重权,回到例题:

要求找出一个边长为 \(R\) 的正方形,使得这个正方形里所有点的权值之和最大。

那么考虑从 \((R,R)\) 开始枚举(因为最少只能是左上角的 \(R\times R\) 的矩形),每次用 sum 数组更新答案。这个答案怎么更新呢?

如图:

技术分享图片

我们希望求出红色部分的权值和,那么我们可以拿整个大矩形,减去绿色的部分得到。那么大概可以得到:

\[ sum_{x,y}-sum_{x-r,y}-sum_{x,y-r} \]

但是仔细观察可以发现,在下图中,蓝色的部分被减去了两次!(\(sum_{x-r,y}\)那个矩形和\(sum_{x,y-r}\)这两个子矩形重合的部分)

技术分享图片

很好办,再把这个矩形的权值和加上即可,所以最后正确找到这个红色矩形的递推式就是:

\[ sum_{x,y}-sum_{x-r,y}-sum_{x,y-r}+sum_{x-r,y-r} \]

写成代码就是

    int ans=-(1<<30); //ans记录答案(最大值)
    for(int i = r; i <= 5001; i++)
        for(int j = r; j <= 5001; j++)
            ans = max(ans, sum[i][j] - sum[i - r][j] - sum[i][j - r] + sum[i - r][j - r]);

完整的AC代码就是

#include <iostream>
#include <stdio.h>
#include <math.h>
#define DEBUG printf("This is OK\n") 

using namespace std;

int n, r, sum[5003][5003];

int main()
{
    cin >> n >> r;
    for(int i = 1; i <= n; i++)
    {
        int x, y, v;
        cin >> x >> y >> v;
        sum[x + 1][y + 1] += v;
    }
    //DEBUG;
    for(int i = 1; i <= 5001; i++)
        for(int j = 1; j <= 5001; j++)
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    //DEBUG;
    int ans=-(1<<30);
    for(int i = r; i <= 5001; i++)
        for(int j = r; j <= 5001; j++)
            ans = max(ans, sum[i][j] - sum[i - r][j] - sum[i][j - r] + sum[i - r][j - r]);
    cout << ans <<endl;
    return 0;
}

注这题卡空间,数组不能开太大。

差分

继续刚刚那个问题,如果不需要查询区间和,而需要把区间加上一个值怎么办办呢?

设 c[i] 表示 a[i] 与 a[i-1] 的差,那么这个 c 数组也可以快速递推出来

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

看看 c 数组长啥样

a: 1 2 3 4 5 6 7 19
c: 0 1 1 1 1 1 1 12

c 数组也就是差分数组

不难看出,差分与前缀和互为逆运算

现在我们手握 c 数组,如何利用她来干事情呢?

如果要把 \([l,r]\) 加上 x ,那么我么可以把 c[l]+x,c[r+1]-x

之所以这么干,道理是 \(a_i(l\le i\le r,i\in \mathbb{Z})\) 进行操作后,我们不去更改 a 数组本身,而是去改变她的差分数组 c 。对这个序列 a 的影响从 l 开始,那么也就是从 l 起,a 中的每一个数都比前一个多 x ,所以把 c[l] 加上 x;这个影响到哪里结束呢?也就是从 a[r+1] 开始,值不会被改变,那么就意味着影响结束了。为了避免前面的改动对后面造成的影响,我们强制把第 r+1 个位置减去 x ,这样一来,就抵消了前面的操作。

用刚刚那个表举个例子,如果要把 \([3,5]\) 内的值都加上 1,那么:

原本:
a: 1 2 3 4 5 6 7 19
c: 1 1 1 1 1 1 1 12
修改后的c:
c: 1 1 2 1 1 0 1 12

如何递推出修改后的 a 呢?很简单,利用原来的 a 序列不断加上 c 的值即可

原本:
a: 1 2 3 4 5 6 7 19
c: 1 1 1 1 1 1 1 12
修改后的c:
c: 1 1 2 1 1 0 1 12
还原a:
a: 1 2 4 5 6 6 7 19

二维差分

似乎挺奇怪的。例题:[洛谷P3397]地毯

一个很朴素的想法是,每当输入一组地毯的坐标时,直接 \(\mathcal{O}(n^2)\) 更新答案(i.e. 把答案所有在这个范围内的都+1).

参考代码:

#include <iostream>
#include <stdio.h>

using namespace std;

int n,m,a[1001][1001];

int main()
{
    cin>>n>>m;
    while(m--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        for(int i=x1;i<=x2;i++)
            for(int j=y1;j<=y2;j++)
                a[i][j]++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<a[i][j]<<" ";
        puts("");
    }
    return 0;
}

此题数据范围太水,这段代码确实能通过;考虑如何优化:记一个二维数组 pre 为差分数组,一开始都为0(没有任何地毯覆盖)。

当输入一组数据 \((x_1,y_1),(x_2,y_2)\) 时,我们扫描 x1 ~ x2(每一行),把每一行对应的列做一个差分。

e.g. 设我们要覆盖 $ a_{i,j}(2\le i,j \le5, i,j\in\mathbb{Z})$ 这个子矩阵,那么有:

一开始
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
差分:
0 0 0 0 0 0
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 0 0 0 0 0

可以看出差分的方法是不变的,只不过变成了每一次做 \(x_2-x_1\) 次差分!

那么代码也就呼之欲出了!

while(m--)
{
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    for(int i=x1;i<=x2;i++) 
    {
        pre[i][y1]++;
        pre[i][y2+1]--;
    }
}

同样的,在输出时分行处理即可。这里有一个技巧:由于一开始的大矩阵也都是 0 ,最后可以直接用 pre 数组递推,从而省区了部分空间。

写法一:

#include <iostream>
#include <stdio.h>

using namespace std;

int n,m,pre[10001][10001],a[10001][10001];

int main()
{
    cin>>n>>m;
    while(m--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        for(int i=x1;i<=x2;i++) 
        {
            pre[i][y1]++;
            pre[i][y2+1]--;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[i][j]=a[i][j-1]+pre[i][j];
            cout<<a[i][j]<<" ";
        }
        puts("");
    }
    return 0;
}

写法二:

#include <iostream>
#include <stdio.h>

using namespace std;

int n,m,pre[10001][10001],a[10001][10001];

int main()
{
    cin>>n>>m;
    while(m--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        for(int i=x1;i<=x2;i++) 
        {
            pre[i][y1]++;
            pre[i][y2+1]--;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            pre[i][j]+=pre[i][j-1]; //直接用 pre 数组推
            cout<<pre[i][j]<<" ";
        }
        puts("");
    }
    return 0;
}

综合练习

[洛谷P3406]海底高铁

(题目有点问题,不是是对于“第i段铁路,需要花Ci博艾元的工本费购买一张IC卡,然后乘坐这段铁路一次就只要扣Bi(Bi<Ai)元。”而是“对于第i段铁路,需要花Ci博艾元的工本费购买一张IC卡,然后乘坐这段铁路一次就只要Bi(Bi<Ai)元。”)

一个显而易见的思路是,对于走过的每一条路,看看使用哪种方法(直接用纸质票还是买 IC 卡)更优。但是注意到一段线路会出现多次,那么就要线记录这一段线路走了多少次再更新答案。

如果直接暴力搞会超时,同上,pre再这题中既是记录次数的数组也是差分数组(这是因为一开始都是0,那么次数和差分两个数组就可以合并。这是很常用的一个技巧)。

然后每次取区间的左端点、右端点,差分即可。然后都弄完后跑一遍前缀和,最后拿着 pre 去找答案就好了。

具体看代码:

#include <iostream>
#include <stdio.h>
#include <math.h>
#define ull unsigned long long

using namespace std;

ull n,m,p[1000010],ans,pre[1000019];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>p[i];
    for(int i=1;i<m;i++)
    {
        ull l=min(p[i],p[i+1]);
        ull r=max(p[i],p[i+1]);
        //数据有可能反过来
        pre[l]++;
        pre[r]--;
    }
    for(int i=1;i<=n;i++) pre[i]+=pre[i-1];
    //差分数组的前缀和就是每一段出现的次数
    for(int i=1;i<n;i++)
    {
        ull a,b,c;
        cin>>a>>b>>c;
        ans+=min(a*pre[i],b*pre[i]+c); 
        //用更优的方案
    }
    cout<<ans<<endl;
    return 0;
}

练习:

[洛谷P1147]连续自然数和

提示:前缀和+枚举+优化

题解

关于前缀和与差分的优劣,请看这里。

【学习笔记】前缀和与差分

原文:https://www.cnblogs.com/BlueInRed/p/12501868.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!