树状数组

树状数组是一种小常数，以 \(O(\log n)\) 时间复杂度动态维护区间可差分信息的数据结构。

在动态维护区间和时，其时间和空间常数均比线段树小 \(\frac{1}{2}\)，且码量很小。

区修区查

我们使用树状数组维护原数组 \(a\) 的差分数组 \(d_i\)。修改时，我们单点修改 \(d_{l}\) 和 \(d_{r+1}\)。查询时，我们发现 \([1,x_0]\) 区间和可以表示为：

\[ \sum_{i=1}^{x_0}{\sum_{j=1}^{i}{d_j}} \]

交换内外求和符号，继续变形：

\[ \begin{align*} &\sum_{i=1}^{x_0}{\sum_{j=i}^{x_0}{d_i}}\\\ =&\sum_{i=1}^{x_0}{(x_0-i+1)d_i}\\\ =&(x_0+1)\sum_{i=1}^{x_0}{d_i}-\sum_{i=1}^{x_0}{id_i} \end{align*} \]

我们用树状数组维护 \(\sum_{i=l}^{r}{d_i}\) 和 \(\sum_{i=l}^{r}{id_i}\)，就能在 \(O(\log n)\) 时间复杂度内实现区修区查。

二维树状数组

同样，使用树状数组可以实现 \(O(\log^2 n)\) 的时间复杂度内实现二维的矩阵修改矩阵求和。

使用和一维树状数组相同的思路，我们写出：

\[ \sum_{i=1}^{x_0}\sum_{j=1}^{y_0}\sum_{i'=1}^{i}\sum_{j'=1}^{j}{d_{i'j'}} \]

应用同样的变形，最后得到：

\[ \sum_{i=1}^{x_0}\sum_{j=1}^{y_0}{\big( xy-(i-1)y-(j-1)x+(i-1)(j-1) \big) d_{ij}} \]

我们使用四个二维树状数组分别维护以下信息：

\[ \begin{align*} tr1:&\sum_{i=1}^{x_0}\sum_{j=1}^{y_0}{(d_{ij})}\\\ tr2:&\sum_{i=1}^{x_0}\sum_{j=1}^{y_0}{(i-1)(d_{ij})}\\\ tr3:&\sum_{i=1}^{x_0}\sum_{j=1}^{y_0}{(j-1)(d_{ij})}\\\ tr4:&\sum_{i=1}^{x_0}\sum_{j=1}^{y_0}{(i-1)(j-1)(d_{ij})} \end{align*} \]

查询时应用如下公式得出答案：

\[ xy(tr1(x_0,y_0))-y(tr2(x_0,y_0))-x(tr3(x_0,y_0))+tr4(x_0,y_0) \]