前缀和和差分

前缀和

每个人对前缀和的含义理解不一样

已知一个前缀和数组sum

下标数字表示的含义为原数组前n个数的和。

例如：

source[10] = {1,2,3,4,5,6,7,8,9,10};
sum[0] = 0		//含义为原数组前0个数的和，所以为0 
sum[1] = 1		//含义为原数组前1个数的和，所以为1 
sum[2] = 3		//含义为原数组前2个数的和，所以为3

前缀和下标和原数组下标不是一一对应

我们常用前缀和求区间的公式为sum[r] - sum[l - 1]

在区间[l,r]上表示从l到r之间的和。

sum[r]表示前r个数的和，sum[l-1]表示前l-1个数的和，我们减去之后就是区间[l,r]

构建前缀和需要特殊处理sum[0]其次sum[i] = sum[i-1]+source[i-1]每一项都是前一项加上一个新的数。

sum[0] = 0;
for(int i = 1;i <= n;i++){
	sum[i] = sum[i - 1] + source[i - 1];
}

查分数组和前缀和数组互为逆运算，通过对差分数组求前缀和可得到原数组

已知一个差分数组sub,差分数组下标的含义为当前项与前一项的差值

1
2
3

sub[0] = source[0] - 0;
sub[1] = source[1] - source[0];
sub[2] = source[2] - source[1];

通过对差分数组求前缀和即可还原原数组,还原数组公式为

1
2
3

for(int i = 1;i < n;i++){
	sub[i] += sub[i-1]; //前一个数加上与当前数的差值,即可还原原数据
}

和前缀和不同的是,前缀和下标0表示的是0个数据的和,所以为0;

而差分数组下标0表示的是第0个数与前一个数的差值,因为已经是第一个数据,所以就是与0的差值,就是其本身

在区间[l,r]加上一个数c我们可以这样表示sub[l] += c,sub[r+1] -= c因为下标表示的是当前数与前一个数之间的差值,所以我们直接在l上加上一个c,在右边界r的下一个数字减去一个c

1 2	sub[l] += c; sub[r+1] -= c;

构建差分数组比较好理解,根据定义我们直接把0落下来,其次分别求与前一个数的差值即可

sub[0] = source[0];
for(int i = 1;i < n;i++){
	sub[i] = source[i] - source[i - 1];
}