树状数组概念及操作

树状数组概念及其操作
在算法竞赛中，有很多操作要求我们对区间内的元素进行处理。如果我们采取模拟，
一个一个的去对单个元素进行操作，很显然时间上肯定接受不了。如下面这个问题：
设计一个算法，用来处理一个序列：1，查询序列中某段区间内的元素和。2，把一段区间都加上一个常数。共k次操作。如果存粹地去模拟，最坏情况下每次操作要遍
历n个元素，k次操作的总复杂度为O(n*k),约为O(n^2)。可以看出该算法很慢。而慢
的主要原因是我们每次都对单个元素进行操作。如果该为对区间进行操作呢？
相信大家刚学算法的时候肯定学过前缀和，定义一个sum[i]数组,表示1—i的元素总
和。但是本题相对于以前的不同点是，每次操作可能是查询，也有可能是更改某个元素
的值。而更改i位置元素的值，势必会影响到后面的sum[i--n]数组，想要不影响，那么还
是要一个一个去修改。因此当更改一个元素后，我们必须想一个快速修改sum[]的方法。
这里我们引进树状数组。
单个单个修改/查询元素是慢的本质所在，只有当我们一块一块的去修改/查询才能够
优化。在无限背包问题中，我们把s[i](s[]表示同一物品的个数)分解为若干个小物品。列如
Si==5，对于b<=5的每一个数，我们可以用若干2^k来把它分解。如b=5=2^2 2^0,
4=2^2,3=2^1 2^0,2=2^1,1=2^0。可以发现这就是在用二进制来表示一个数。而把一个
数拆成这个形式，只需log2(n)次。如果我们把sum[i]分解成这些数的和，那么查询时间
就是log级别的了。要比前缀和慢。但如果修改操作也是log级别的话，总复杂度就是
O(k*log2(n))。
树状数组就是这样的一种数据结构，可以轻松解决。我们把一个数写成二进制形式
5=101，我们让每一个含一的位置储存数原先数组中的若干个数，且为2^k个。我们查询
Sum[5]时可以直接向k==1,k==2这个两个位置要，即拆成若干个子集和。如下图(本文图片均来自林厚从—高级数据结构一书)
可以看出每段区间对应的数的二进制数最右边的1及以后的数就是对应每个区间储存的元素个数，归纳如下：
现在问题来了，我们只要能把每个末尾的1和它后面的0提取出来，找到相应的区间，
然后都加在一块即可。在这里需要用到二进制中lowbit(x)操作。对于x,它返回x&-x.
-x表示一个数的反码，即原二进制各位取反后 1. 如二进制 1…010000，-x=0…110000,
X&-x=10000。既可以把末尾1和后面的0，提取出来了。对于6—1我们只要一直往左