树状数组 ( Binary Indexed Tree，BIT，二分索引树 )

﹏ヽ暗。殇╰゛Y 2021-09-14 09:36 254阅读 0赞

百度很多树状数组，唯有此篇一看就懂。  
[原文][Link 1]

## **一、简介** ##

在有时，需要计算数组某个区间内的和，如果采用常规算法，每次求和时遍历一遍求和比较耗时间，而树状数组维护一个求和数组，将原数组的一些求和结果存在数组中，使用时直接用树状数组求和。最常用的求区间和问题，单点更新。

## **二、建树** ##

![这里写图片描述][SouthEast]  
**结构：**  
如上A代表原数组，而C代表树状数组。树状数组具有数组和树两个特性，在存储上以数组形式按顺序存储，在逻辑关系上，通过数组下标表示树的父子关系。对于两个数组下标x，y(x < y)，如果x + 2^k = y (k等于x的二进制表示中末尾0的个数)，那么定义(y, x)为一组树上的父子关系，其中y为父结点，x为子结点。如上图树状数组的第4个元素C4的父结点为C8 (4的二进制表示为100，所以k=2，那么4 + 2^2 = 8)，而奇数下标的一定是叶子结点。  
**节点：**  
节点Ci表示的其实是一段原数组A的连续区间和。根据定义，右区间是很明显的，一定是i，即Ci表示的区间的最后一个元素一定是Ai，那么接下来就是要求Ci表示的第一个元素是什么。从图上可以很容易的清楚，其实就是顺着Ci的最左儿子一直找直到找到叶子结点，那个叶子结点就是Ci表示区间的第一个元素。  
更加具体的，如果i的二进制表示为 ABCDE1000，那么它最左边的儿子就是 ABCDE0100，这一步是通过结点父子关系的定义进行逆推得到，并且这条路径可以表示如下：  
ABCDE1000 => ABCDE0100 => ABCDE0010 => ABCDE0001  
这时候，ABCDE0001已经是叶子结点了，所以它就是Ci能够表示的第一个元素的下标，那么我们发现，如果用k来表示i的二进制末尾0的个数，Ci能够表示的A数组的区间的元素个数为2^k，又因为区间和的最后一个数一定是Ai，所以有如下公式：  
Ci = sum\{ A\[j\] | i – 2^k+ 1 <= j <= i \} （帮助理解：将j的两个端点相减+1 等于2^k）  
**求和：**  
sum(i) = sum\{ A\[j\] | 1 <= j <= i \}  
= A\[1\] + A\[2\] + … + A\[i\]  
= A\[1\] + A\[2\] + A\[i-2^k\] + A\[i-2^k+1\] + … + A\[i\]  
= A\[1\] + A\[2\] + A\[i-2^k\] + C\[i\]  
= sum(i – 2^k) + C\[i\]  
= sum( i – lowbit(i) ) + C\[i\]

int sum(int x){
         int s =0;
         for(int i = x; i>0; i -= lowbit(i)){
             s += c[i];
         }
         return s;    
    }

**更新：**  
add(i, v)，表示的其实就是 A\[i\] = A\[i\] + v。但是我们不能在原数组A上操作，而是要像求和操作一样，在树状数组C上进行操作。  
那么其实就是求在Ai改变的时候会影响哪些Ci，看图的树形结构就一目了然了，Ai的改变只会影响Ci及其祖先结点，即A5的改变影响的是C5、C6、C8；而A1的改变影响的是C1、C2、C4、C8。也就是每次add(i, v)，我们只要更新Ci以及它的祖先结点。

void add(int x,int v){
        for(int i = x; i <= n; i += lowbit(i)){
            C[i] += v;
        }
    }

**lowbit：**  
函数lowbit(x)，表示的是x的二进制表示末尾0的个数。

来看一段补码小知识：清楚补码的表示的可以跳过这一段，计算机中的符号数有三种表示方法，即原码、反码和补码。三种表示方法均有符号位和数值位两部分，符号位都是用0表示“正”，用1表示“负”，而数值位，三种表示方法各不相同。这里只讨论整数补码的情况，在计算机系统中，数值一律用补码来表示和存储。原因在于，使用补码，可以将符号位和数值域统一处理；同时，加法和减法也可以统一处理。整数补码的表示分两种：

正数：正数的补码即其二进制表示；例如一个8位二进制的整数+5，它的补码就是 00000101 （标红的是符号位，0表示”正”，1表示“负”）

负数：负数的补码即将其整数对应的二进制表示所有位取反(包括符号位)后+1；例如一个8位二进制的整数-5，它的二进制表示是00000101，取反后为11111010，再+1就是11111011，这就是它的补码了。

下面的等式可以帮助理解补码在计算机中是如何工作的：  
\+5 + (-5) = 00000101 + 11111011 = 1 00000000 (溢出了!!!) = 0这里的加法没有将数值位和符号位分开，而是统一作为二进制位进行计算，由于表示的是8进制的整数，所以多出的那个最高位的1会直接舍去，使得结果变成了0，而实际的十进制计算结果也是0，正确。

补码复习完毕，那么来看下下面这个表达式的含义：x & (-x) (其中 x >= 0)

首先进行&运算，我们需要将x和-x都转化成补码，然后再看&之后会发生什么，我们假设 x 的二进制表示的末尾是连续的 k 个 0，令x的二进制表示为 X0X1X2…Xn-2Xn-1, 则 \{Xi = 0 | n-k <= i < n\}， 这里的X0表示符号位。

x的补码就是由三部分组成：(0)(X1X2…Xn-k-1)(k个0) 其中Xn-k-1为1，因为末尾是k个0，如果它为0，那就变成k+1个0了。

\-x的补码也是由三部分组成：(1)(Y1Y2…Yn-k-1)(k个0) 其中Yn-k-1为1，其它的Xi和Yi相加为1，想想补码是怎么计算的就明白了。

那么 x & (-x) 也就显而易见了，由两部分组成 (1)(k个0)，表示成十进制为 2k 啦。由于&的优先级低于-，所以代码可以这样写：

int lowbit(int x) {
         return x & -x;
    }

## **三、样例** ##

[CCF 除法][CCF]

[Link 1]: http://blog.jobbole.com/96430/
[SouthEast]: /images/20210520/8b2f7169859940309cafdb3ec76967b5.png
[CCF]: http://blog.csdn.net/qq_16234613/article/details/78534262