有一个包含 n 个数的数列2, 7, 1, 12, 5, 9 …，请计算前 i 个数的和值，即前缀和sum[ i ]= a [1]+ a [2]+…+ a [ i ]（ i =1, 2, …, n ）。该怎么计算呢？一个一个加起来怎么样？

若用这种办法，则计算前 n 个数的和值需要 O ( n )时间。而且若对 a [ i ]进行修改，则对sum[ i ], sum[ i +1], …, sum[ n ]都需要修改，在最坏的情况下需要 O ( n )时间。当 n 特别大时效率很低。

树状数组可以高效地计算数列的前缀和，其查询前缀和与点更新（修改）操作都可以在 O (log n )时间内完成，那么树状数组是怎么巧妙实现这些的呢？

1. 树状数组的由来

树状数组引入了分级管理制度且设置了一个管理小组，管理小组中的每个成员都管理一个或多个连续的元素。例如，在数列中有9个元素，分别用 a [1], a [2], …, a [9]存储，还设置了一个管理小组 c []。

管理小组的每个成员都存储其所有子节点的和。

· c [1]：存储 a [1]的值。

· c [2]：存储 c [1]、 a [2]的和值，相当于存储 a [1]、 a [2]的和值。

· c [3]：存储 a [3]的值。

· c [4]：存储 c [2]、 c [3]、 a [4]的和值，相当于存储 a [1]、 a [2]、 a [3]、 a [4]的和值。

· c [5]：存储 a [5]的值。

· c [6]：存储 c [5]、 a [6]的和值，相当于存储 a [5]、 a [6]的和值。

· c [7]：存储 a [7]的值。

· c [8]：存储 c [4]、 c [6]、 c [7]、 a [8]的和值，相当于存储 a [1]～ a [8]的和值。

· c [9]：存储 a [9]的值。

从上图可以看出，这个管理数组 c []是树状的，因此叫作树状数组。怎么利用树状数组求前缀和及点更新呢？

1）查询前缀和

若想知道sum[7]，则只需 c [7]加上左侧所有子树的根即可，即sum[7]= c [4]+ c [6]+ c [7]。

· sum[4]：左侧没有子树，直接找 c [4]即可，sum[4]= c [4]。

· sum[5]：左侧有一颗子树，其根为 c [4]，sum[5]= c [4]+ c [5]。

· sum[9]：左侧有一棵子树，其根为 c [8]，sum[9]= c [8]+ c [9]。

2）点更新

点更新指修改一个元素的值，例如对 a [5]加上一个数 y ，则需要更新该元素的所有祖先节点，即 c [5]、 c [6]、 c [8]，令这些节点都加上 y 即可，对其他节点都不需要修改。

为什么只修改其祖先节点呢？因为当前节点只和祖先有关系，和其他节点没有关系。

· c [5]：存储 a [5]的值，修改 a [5]加上 y ，因此 c [5]也要加上 y 。

· c [6]：存储 c [5]、 a [6]的和值（ a [5]、 a [6]）， a [5]加上 y ， c [6]也要加上 y 。

· c [8]：存储 c [4]、 c [6]、 c [7]、 a [8]的和值（～ a [1] a [8]）， a [5]加上 y ， c [8]也要加上 y 。

那么这个管理数组（树状数组）是怎么得来的呢？下面详细讲解。

2. 树状数组的实现

树状数组，又叫作二进制索引树（Binary Indexed Trees），通过二进制分解划分区间。那么 c [ i ]存储的是哪些值？

1）区间长度

若 i 的二进制表示末尾有 k 个连续的0，则 c [ i ]存储的区间长度为2 k ，从 a [ i ]向前数2 k 个元素，即 c [ i ]= a [ i -2 k +1]+ a [ i -2 k +2]+…+ a [ i ]。

例如： i =6，6的二进制表示为110，末尾有1个0，即 c [6]存储的值区间长度为2（2 1 ），存储的是 a [5]、 a [6]的和值，即 c [6]= a [5]+ a [6]。

i =5，5的二进制表示为101，末尾有0个0，即 c [5]存储的值区间长度为1（2 0 ），它存储的是 a [5]的值，即 c [5]= a [5]。动手试一试，其他值是不是也这样？

怎么得到这个区间的长度呢？若 i 的二进制表示末尾有 k 个连续的0，则 c [ i ]存储的值区间长度为2 k ，换句话说，区间长度就是 i 的二进制表示下最低位的1及它后面的0构成的数值。例如 i =20，其二进制表示为10100，末尾有两个0，区间长度为2 2 （4），其实就是10100最低位的1及其后面的0构成的数值100（该数为二进制，其十进制为4）。

怎么得到100呢？可以先把10100取反，得到01011，然后加1得到01100，此时，最低位的1仍然为1，而该位前面的其他位与原值相反，因此与原值10100进行与运算即可。

· 取反运算（～）：1变成0，0变成1。

· 与运算（&）：两位都是1，则为1，否则为0。

在计算机中二进制数采用的是补码表示，- i 的补码正好是 i 取反加1，因此(- i )& i 就是区间的长度。若将 c [ i ]存储的值区间长度用lowbit( i )表示，则lowbit( i )=(- i )& i 。

算法代码：

2）前驱和后继

直接前驱： c [ i ]的直接前驱为 c [ i -lowbit( i )]，即 c [ i ]左侧紧邻的子树的根。

直接后继： c [ i ]的直接后继为 c [ i +lowbit( i )]，即 c [ i ]的父节点。

前驱： c [ i ]的直接前驱、其直接前驱的直接前驱等，即 c [ i ]左侧所有子树的根。

后继： c [ i ]的直接后继，其直接后继的直接后继等，即 c [ i ]的所有祖先。

c [7]的直接前驱为 c [6]， c [6]的直接前驱为 c [4]， c [4]没有直接前驱； c [7]的前驱为 c [6]、 c [4]。

c [5]的直接后继为 c [6]， c [6]的直接后继为 c [8]， c [8]没有直接后继； c [5]的后继为 c [6]、 c [8]。

3）查询前缀和

前 i 个元素的前缀和sum[ i ]等于 c [ i ]加上 c [ i ]的前驱，sum[7]等于 c [7]加上 c [7]的前驱， c [7]的前驱为 c [6]、 c [4]，因此sum[7]= c [7]+ c [6]+ c [4]。

算法代码：

4）点更新

若对 a [ i ]进行修改，令 a [ i ]加上一个数 z ，则只需更新 c [ i ]及其后继（祖先），即令这些节点都加上 z 即可，不需要修改其他节点。修改 a [5]，另其加上2，则只需 c [5]+2，对 c [5]的后继分别加上2，即 c [6]+2、 c [8]+2。

算法代码：

注意：树状数组的下标从1开始，不可以从0开始，因为lowbit(0)=0时会出现死循环。

5）查询区间和

若求区间和值 a [ i ]+ a [ i +1]+…+ a [ j ]，则求解前 j 个元素的和值减去前 i -1个元素的和值即可，即sum[ j ]-sum[ i -1]。

算法代码：

3. 算法分析

树状数组是通过二进制分解划分区间的。树状数组的性能与 n 的二进制位数有关， n 的二进制位数为 ， 表示向下取整，即取小于或等于 x 的最大整数。 =2，5的二进制位数为3位； =3，8的二进制位数为4。

如何求解树状数组的高度呢？树状数组底层的叶子是 c [1]，因此从开始一直找其后继（祖先）直到树根，就是树状数组的高度。 c [1]- c [2 1 ]- c [2 2 ]- c [2 3 ]-…- c [ n ]，每次都是2倍增长，假设 n =2 x ，则 x =log n ，因此树高 h = O (log n )。更新时，从叶子更新到树根，执行的次数不超过树的高度，因此更新的时间复杂度为 O (log n )。

查询前缀和时，需要不停地查找前驱，那么前驱最多有多少个呢？ n 的二进制数有 k = 位，在最多的情况下，每一位都是1，则 n =“111…1”可以被表示为 n =2 k -1 +2 k -2 +…+2 1 +2 0 。7=“111”=2 2 +2 1 +2 0 ， c [7]的前驱为 c [7-2 0 ]、c[7-2 0 -2 1 ]、 c [7-2 0 -2 1 -2 2 ]，最后一个为 c [0]，表示不存在，因此 c [7]的前驱为 c [6]、 c [4]。前驱的个数与 n 的二进制数的位数有关，不超过 O (log n )，因此查询前缀和的时间复杂度为 O (log n )，即树状数组修改和查询的时间复杂度均为 O (log n )。 OaOoskqIjSpoAWtSFTnlFuIG3mguUBO8ytT97QcyQGfnLy6sCRu3/BcEWbW8TgC/