河北大学暑期程序设计训练每日知识分享-day18

每日分享——前缀和&差分

前缀和：

给定一个长度为n的序列，当我们需要频繁的求某一段区间内的和的时候，我们可以使用 前缀和 来减少运算次数。

前缀和是一个典型的以空间换时间的小技巧。其实就是我们高中学过的前n项和。

给定一个数组 a[n],我们使用s[i]来表示a[]的前i项和。

1
2
3
4
5
//a[]的有效数据从1开始 1~n

//构造前n项和s[n]
s[0]=0;
for(int i=1;i<=n;++i) s[i]=s[i-1]+q[i];

因为循环中需要用到i-1我们的下标从1开始避免错误，所以可以让a[]数组从1开始存储有效数据。（当我们程序中用到[i-1]时，经常下标从1开始）。

查询第l个数到第r个数的和：

1
2
3
4
5
6
7
int getSum(int l,int r)
{
	return s[r]-s[l-1];
    //s[r]:   a[1]+...+a[r]
    //s[l-1]: a[1]+...+a[l-1]
    //        a[l]+...+a[r]
}

今年上半年的csp的第二题就可以使用这个技巧（只不过是二维的）。

差分：

给定一个长度为n的序列，当我们需要频繁的对某一段区间内的每一个值进行相同的操作时，我们可以使用 差分 来减少运算次数。

差分就是前缀和的逆运算。对差分求前缀和就是序列的值。

给定一个序列a[n]，然后我们构造一个数组b[n]：使得

1
a[i] = b[1] +...+ b[i];

这时我们称b数组为a的差分数组。

先看看主要操作：在[l,r]区间内的每个数都加上c。

1
2
3
4
void insert(int l,int r,int c)
{
    b[l]+=c,b[r+1]-=c;
}

解释：

b[l]+=c:
a[l]到a[n] 都加上了c

b[r+1]-=c;
a[r+1]到a[n] 都减去了c

所以： a[l]到a[r]都加上了c

这个里面我们不用考虑构造。换言之构造可以想象成每个a[i]都是一个插入操作。

1
for(int i=1;i<=n;++i) insert(i,i,a[i]);

进行完插入操作后，最后我们得到改变后的a[i]数组 求一遍b的前缀和即可。

1
2
for(int i =1;i<=n;++i) b[i]=b[i]+b[i-1];
// b->a得到差分的前缀和 即 a[i]

（大胆预测一下，未来某次csp的第二题或许会使用到此技巧。）