树状数组解决数组单点更新后快速查询区间和的问题

作者：Grey

原文地址：树状数组解决数组单点更新后快速查询区间和的问题

数组在不变的情况下，前缀和数组可以用来加速生成<code>i ~ j</code>位置的累加和信息, 假设前缀和数组为<code>preSum</code>，那么<code>i...j</code>的累加和

<code>sum[i...j] = preSum[j] - preSum[i-1]</code>

但是如果数组要单点修改，则以上的情况不适用，树状数组(index tree)就是解决这个问题，时间复杂度可以达到O(logN)。

注：本文所有涉及到的数组操作均从下标1开始计算，下标0位置弃而不用

申请一个辅助数组<code>help</code>, 大小和原始数组<code>arr</code>一样，保存原始数组的累加信息，但是要基于如下规则来保存。

遍历的位置i如果是奇数，则只管自己这个位置的内容，即：<code>arr[i] = help[i]</code>。

遍历的位置i如果是偶数，则按如下规律：

<code>0010</code>管<code>0001 ~ 0010</code>的累加和，

<code>00100</code> 管 <code>00001 ~ 00100</code>的累加和，

<code>0110</code> 管 <code>0101 ~ 0110</code>的累加和

...

即某个偶数位置接管的区间是：把这个偶数位置二进制最右边的1抹掉后再加1得出的位置一直到这个位置本身。

比如：

<code>1010111000</code>这个位置，把最右边的1抹掉后，值为<code>1010110000</code>,再加1，值为<code>1010110001</code>,所以<code>1010111000</code>这个位置接管的累加和是从<code>1010110001 ~ 1010111000</code>。

通过以上做法生成<code>help</code>数组后，我们可以通过这个<code>help</code>数组快速响应单点更新，并快速求得前缀和。

按如上流程生成<code>help</code>数组后，如果要计算<code>1..i</code>位置的累加和，则有如下规则：

第一步，提取出i最右侧的1，假设为x，将<code>help[i] + help[i-x]</code>，得出a1

第二步，继续提取i-x最右侧的1，假设为y，将<code>a + help[i- x - y]</code>，得出a2

直到i提取完所有最右侧的1，求累加，得到的结果即为<code>1...i</code>上的累加和。

其中<code>index&amp;-index</code>即为index最右侧的1。

如果单点有更新，比如需要在index位置上的值增加一个d，此时需要考虑哪些位置受到了牵连。

<code>单点的二进制最末尾的1加1，依次到数组结尾，都是受到牵连的位置</code>

<code>index += index &amp; -index;</code> 即为受到牵连的位置，所以这些位置都要执行加d的操作。

线段树是树状数组的升级版，树状数组只能做到单点更新后，维持累加和信息的快速更新，线段树可以支持范围更新，但是树状数组可以很方便改成二维或者三维的，对于线段树来说，改成二维的太复杂。

二维树状数组主要解决：在单点变化时候，快速更新从左上角位置<code>（1,1）</code>累加到<code>(i,j)</code>位置的累加和信息这个问题。

熟悉一维数组后，二维的树状数组比较简单，原先一维数组只需要考虑<code>1...i</code>位置累加和，现在二维除了考虑<code>1...i</code>位置累加和，还要考虑<code>1...j</code>位置的累加和

二维树状数组的<code>sum</code>方法和<code>update</code>方法如下

即在一维的条件下，增加了一个循环。

现在有了二维树状数组，如果要求整个二维平面中，任意<code>[row1,col1]</code>位置到<code>[row2,col2]</code>位置组成的矩形累加和信息，则可以很方便通过二维数状数组计算出来：

segment-tree

binary-indexed-tree

算法和数据结构笔记

程序员代码面试指南（第2版）

算法和数据结构体系班-左程云