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

这个东西的用途其实不太大，复杂的区间信息还是靠线段树，而且这个操作线段树能直接干了。

主要应用在以下两个方面：

1、区间加数，区间求和问题。

2、区间加等差数列，单点求值问题。

①可以用线段树直接干，②可以维护差分数组转化为①。

虽然在一维中是个几乎无用的技巧，但是二维的矩形区间加，求矩形和类的问题，四分树以及树套树又不好写，所以可以用二维的树状数组通过这种技巧实现。

为了处理数组越位以及树状数组中0无法被查询的问题，下标从1开始计算。

前缀和的前缀和

设 $s_1$ 表示数组a的前缀和， $s_2$ 表示 $s_1$ 的前缀和，则有

$\begin{align*} s_1[i] &=\sum_{j=1}^{i}a[j] \\ s_2[i] &=\sum_{j=1}^{i}s_1[j] \end{align*}$

那么将 $s_1$ 代入 $s_2$ 中的 $s_1$ 则有

$\begin{align*} s_2[i] &=\sum_{j=1}^{i}s_1[j] \\ s_2[i] &=\sum_{j=1}^{i} \sum_{k=1}^{j}a[k]\\ s_2[i] &=\sum_{j=1}^{i}(i-j+1)a[j] \end{align*}$

很明显这个东西，也就是 $s_2[i]=\sum_{j=1}^{i}(i-j+1)a[j]$ 没法用树状数组或者线段树维护，因为i是作为查询参数的变量，树状数组和线段树里面储存的信息不能随着查询参数变化。

继续变形

$\begin{align*} s_2[i] &=\sum_{j=1}^{i}(i-j+1)a[j] \\ s_2[i] &= \sum_{j=1}^{i}((i+1)a[j]-j*a[j])\\ s_2[i] &=\sum_{j=1}^{i}(i+1)a[j]+\sum_{j=1}^{i}-j*a[j] \\ s_2[i] &=(i+1)\sum_{j=1}^{i}a[j]-\sum_{j=1}^{i}j*a[j] \end{align*}$

到这里，我们发现 $\sum_{j=1}^{i}a[j]$ 这个东西其实就是 $s_1[i]$ ，而 $\sum_{j=1}^{i}j*a[j]$ 可以看成是一个新的数组，这个数组的值为 $j*a\left[ j \right]$ 的前缀和。

然后开两个树状数组维护这两个前缀和即可。

二维前缀和的前缀和

公式推导过程跟一维一样。

设 $s_1$ 表示数组a的前缀和， $s_2$ 表示 $s_1$ 的前缀和，则有

$\begin{align*} s_1[i][j]&=\sum_{p=1}^{i} \sum_{q=1}^{j}a[p][q] \\ s_2[i][j] &=\sum_{p=1}^{i} \sum_{q=1}^{j}s_1[p][q] \end{align*}$

然后把它代进去...个屁，代进去我可不会算，因为得到了

$\begin{align*} s_2[i][j]=\sum_{p=1}^{i} \sum_{q=1}^{j}s_1[p][q] =\sum_{p=1}^{i} \sum_{q=1}^{j} \sum_{x=1}^{p} \sum_{y=1}^{q}a[x][y] \end{align*}$

额...其实也能算，但是有另一种更为巧妙的算法。

首先是我们知道在一维数组中 $s_2$ 与a的关系： $s_2[i] =\sum_{j=1}^{i}(i-j+1)a[j]$

二维数组的前缀和可以理解为：先对第一个维度做前缀和，再对第二个维度做前缀和。

有了这个认识，我们可以直接将 $s_2[i] =\sum_{j=1}^{i}(i-j+1)a[j]$ 这个式子扩展为 $s_2[i][j] =\sum_{p=1}^{i}(i-p+1)(\sum_{q=1}^{j}(j-q+1)a[i][j])$

$s_2[i][j] =\sum_{p=1}^{i}(i-p+1)(\sum_{q=1}^{j}(j-q+1)a[i][j])$

整理一下，求和符号提前后得到 $s_2[i][j] =\sum_{p=1}^{i} \sum_{q=1}^{j}(i-p+1)(j-q+1)a[i][j]$ 。

然后因为树状数组和线段树里面储存的信息不能随着查询参数变化。

所以还得继续拆分变形。

$\begin{align*} s_2[i][j] &=\sum_{p=1}^{i} \sum_{q=1}^{j}(i-p+1)(j-q+1)a[p][q] \\ s_2[i][j] &=\sum_{p=1}^{i} \sum_{q=1}^{j}((i+1)-p)((j+1)-q)a[p][q]\\ s_2[i][j] &=\sum_{p=1}^{i} \sum_{q=1}^{j}((i+1)(j+1)-p(j+1)-q(i+1)+pq)a[p][q]\\ s_2[i][j] &=(i+1)(j+1)\sum_{p=1}^{i} \sum_{q=1}^{j}a[p][q]-(j+1)\sum_{p=1}^{i} \sum_{q=1}^{j}p*a[p][q]-(i+1)\sum_{p=1}^{i} \sum_{q=1}^{j}q*a[p][q]+\sum_{p=1}^{i} \sum_{q=1}^{j}pq*a[p][q] \end{align*}$

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