树状数组维护前缀和的前缀和

这个东西的用途其实不太大,复杂的区间信息还是靠线段树,而且这个操作线段树能直接干了。
主要应用在以下两个方面:
1、区间加数,区间求和问题。
2、区间加等差数列,单点求值问题。
①可以用线段树直接干,②可以维护差分数组转化为①。
虽然在一维中是个几乎无用的技巧,但是二维的矩形区间加,求矩形和类的问题,四分树以及树套树又不好写,所以可以用二维的树状数组通过这种技巧实现。
为了处理数组越位以及树状数组中0无法被查询的问题,下标从1开始计算。

前缀和的前缀和

s_1表示数组a的前缀和,s_2表示s_1的前缀和,则有

那么将s_1代入s_2中的s_1则有
很明显这个东西,也就是没法用树状数组或者线段树维护,因为i是作为查询参数的变量,树状数组和线段树里面储存的信息不能随着查询参数变化
继续变形

到这里,我们发现这个东西其实就是,而可以看成是一个新的数组,这个数组的值为的前缀和。
然后开两个树状数组维护这两个前缀和即可。

二维前缀和的前缀和

公式推导过程跟一维一样。
s_1表示数组a的前缀和,s_2表示s_1的前缀和,则有

然后把它代进去...个屁,代进去我可不会算,因为得到了
额...其实也能算,但是有另一种更为巧妙的算法。
首先是我们知道在一维数组中s_2与a的关系:
二维数组的前缀和可以理解为:先对第一个维度做前缀和,再对第二个维度做前缀和。
有了这个认识,我们可以直接将这个式子扩展为

整理一下,求和符号提前后得到
然后因为树状数组和线段树里面储存的信息不能随着查询参数变化。
所以还得继续拆分变形。

那么到这一步,已经可以利用二维树状数组处理矩形区间加数,矩形区间求和类的问题,从而避开使用树套树或者四分树。