前缀和与差分

前缀和

前缀和介绍

其实前缀和与其说是一种算法，倒不如说是一个小技巧，在各类算法题中几乎不会单独出现，但却是很多算法题的关键步骤，而很多时候我们又会忘记使用这个小技巧从而导致超时。

前缀和思想

对数组a[ ]建立一个新的数组s[ ],s[i]表示 a[1] + a[2] + .. + a[i]的和

数组s[ ]的作用就是快速求出区间[l, r]的区间和，一般适用在在数据很大时会频繁对数列进行求和的情况下,每次计算区间和的时间复杂度减少到o(1)。

前缀和模板

假设是对数组a[]的区间[l, r]进行求和

void init_presum(int a[], int s[]){//构造前缀和s[]数组
    for(int i = 1; i <= N; i ++ ) s[i] = s[i - 1] + a[i];
    //注：s[]数组初始情况下s[0]默认为0，这样可以更好的处理边界问题
}
int find_presum(int a[], int l, int r){//使用s[]数组进行查询区间和
   return s[r] - s[l - 1]; 
}

其实还有二维的前缀和，思路和一维差不多，也很容易写出来这里就不多进行阐述了。

差分

差分思想

之所以把差分和前缀和放在一起写是因为差分其实就是前缀和的逆操作。

我们仍基于数组a[ ]构造一个新数组b[ ],而a[i]表示数组b[1] + b[2] + .. +b[i]的和。

这样单纯的看起来好像觉得数组b[ ]没啥用，可实际上在规模庞大的数据基础上如果要频繁的修改某些区间上的值时，这个技巧就很适用，可以将原本o(n)的时间复杂度降到o(1)。

具体的操作就当修改区间[l, r]时，不用从原数组a[ ]中一个个改，只需要修改数组b[l]、 b[r + 1]的值就可以了，通过b[ ]能很轻松的更新a[ ]

差分模板

void insert(int l, int r, int c){
    b[l] += c;
    b[r + q] -=c;
}
for (int i = 1; i <= n; i ++ ) b[i] = insert(i, i, a[i]);//数组b[]的构建
//将a[]视为全0的数组，因此b[]一开始也是全0。b可以将a的初始化视为对区间长度为1的'点'进行修改实现自己的构建

同理，二维差分也是存在的，思路还是差不多，这里就不重复写了。

回过头来再思考前缀和与差分…区间查询和修改…这不是和线段树的功能有些相似吗？