河北大学暑期程序设计训练每日知识分享-day18
每日分享——前缀和&差分
前缀和:
给定一个长度为n的序列,当我们需要频繁的求某一段区间内的和的时候,我们可以使用 前缀和 来减少运算次数。
前缀和是一个典型的以空间换时间的小技巧。其实就是我们高中学过的前n项和。
给定一个数组 a[n],我们使用s[i]来表示a[]的前i项和。
1 | //a[]的有效数据从1开始 1~n |
因为循环中需要用到i-1我们的下标从1开始避免错误,所以可以让a[]数组从1开始存储有效数据。(当我们程序中用到[i-1]时,经常下标从1开始)。
查询第l个数到第r个数的和:
1 | int getSum(int l,int r) |
今年上半年的csp的第二题就可以使用这个技巧(只不过是二维的)。
差分:
给定一个长度为n的序列,当我们需要频繁的对某一段区间内的每一个值进行相同的操作时,我们可以使用 差分 来减少运算次数。
差分就是前缀和的逆运算。对差分求前缀和就是序列的值。
给定一个序列a[n],然后我们构造一个数组b[n]:使得
1 | a[i] = b[1] +...+ b[i]; |
这时我们称b数组为a的差分数组。
先看看主要操作:在[l,r]区间内的每个数都加上c。
1 | void insert(int l,int r,int 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 | for(int i =1;i<=n;++i) b[i]=b[i]+b[i-1]; |
(大胆预测一下,未来某次csp的第二题或许会使用到此技巧。)