前缀和数组与差分数组

首先，介绍一下前缀和数组与差分数组是干什么用的，它们主要用在对数组中某一区间中的元素进行操作，例如对a数组中第10到20这个区间中的每一个元素都加上一个数，或者求该区间中所有元素的和，你可能会想到利用对数组进行遍历来实现，但是如果当数据量很大的时候，显然这个方法有些笨拙（时间复杂度过高，提交oj时可能会超时）了，于是就有了下面我们要利用的前缀和数组与差分数组。

首先，我们先来讲一下前缀和数组：

现在有一个数组a，我们想要求它[k,n]这个区间中所有元素的和，然后我们为了处理起来方便，我们构建一个数组b，使它满足b[n]=b[n-1]+a[n].

首先我们对数组b进行观察发现：

b[1]=a[1]

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

b[3]=b[2]+a[3]

这里我们会发现b[2]刚好就是a[1]+a[2],b[3]就是a[1]+a[2]+a[3]

所以b[3]就表示a数组的前3项和，b[n]就表示a数组的前n项和

那么如果我们想求a数组中某个区间的和，就可以借助b数组来求

具体方法如下：

假设我们要求a数组中[k,n]这个区间中所有元素的和,其中很明显k

b[n]=a[1]+a[2]+…+a[k]+…a[n]

b[k]=a[1]+a[2]+…+a[k]

所以b[n]-b[k]得到的就是a[k+1]至a[n]这两个元素之间所有元素的和，跟我们要求的还有一点差别

所以我们改进一下，改进之后得到：b[n]-b[k-1]就是[k,n]区间所有元素的和。

接下来我们再来介绍差分数组：

现在有一个数组a，我们想要对区间[l,r]之间的每一个元素加2，然后我们为了处理起来方便，我们构建一个数组b，使它满足b[n]=a[n]-a[n-1]和a[n]=b[n]+a[n-1]。（这两个式子不知道怎么出来的也没关系，记住就行）

现在我们想要对a数组中区间[l,r]之间的每一个元素加2，我们先来看一下a数组。

a[1]=b[1]

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

a[3]=b[3]+a[2]

a[4]=b[4]+a[3]

我们先对b[3]+2,那么现在b[3]就变成了b[3]+2,即b[3]=b[3]+2，然后我们把b[3]=b[3]+2代入就会发现：

a[1]=b[1]

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

a[3]=b[3]+a[2]=b[3]+a[2]+2

a[4]=b[4]+a[3]=b[4]+a[3]+2

从a[3]开始往后的每一个元素都加了一个2

所以说对b数组中的b[3]加一个2之后，那么在a数组中从第3个元素开始一直到a数组的最后一个元素，所有元素都会加上一个2。

那么现在我们要对数组a中的区间[l,r]之间的每一个元素加2，就只需要先对b[l]+2(就相当于对a[l]到n之间的每一个元素加2)，我们想要的是加到r就行了，所以说需要再减去，即对a[r+1]到a[n]这个区间的元素减去一个2（具体操作为b[r+1]-2,b[r+1]-2就相当与对区间[r+1,n]加上一个-2，就相当于减去2了）。下面附上一张图方便理解。

最后总结对差分数组总结一下：

例如要对a数组的[l,r]区间的元素加上一个2，那么对b数组进行的操作就是

先让b[l]+2，再b[r+1]-2就行了。

下面附上两个例题：

1.（前缀和数组） 

输入输出样例

示例

输入

10 3
7 5 6 4 2 5 0 8 5 3
1 5
2 6
3 7

输出

24
22
17

代码如下：

#include 
using namespace std;
int a[100005];
int b[100005];
int main()
{int n;int m;int c[10000];//c数组用来存放结果 cin >> n >> m;for (int i = 1; i <= n; i++)//输入a数组的时候，直接构建b数组 {cin >> a[i];b[i]=b[i-1]+a[i];}int j=0;while (m > 0)//一共查询m次 {m--;int l, r;cin >> l >> r;c[j]=b[r]-b[l-1];//用c数组来存放结果j++;}for(int i=0;i

500 3
150 300 4
100 200 20
470 471 19

2662

#include
using namespace std;
int b[1000005];
int a[1000005]; 
int main()
{int n;int m;//m个区间for(int i=1;i<=n;i++)//先利用a数组把b数组构建出来，其中a是原数组 {b[i]=a[i]-a[n-1];//由于本题的初始是两个数组都为零，此步奏可以省去 }cin>>n>>m;while(m--){int l,r,value;cin>>l>>r>>value;b[l+1]+=value;b[r+2]-=value;//将数组整体向右移了一位 } for(int i=1;i<=n;i++)//对b数组进行了操作后，再对a数组进行区间修改 {a[i]=b[i]+a[i-1];//可以与之前的递推联系起来更好理解 }int sum=0;for(int i=1;i<=n;i++)//刚开始b数组中的元素为零，经过操作后变成了每棵树需要的费用 {sum+=a[i];}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！