树状数组

树状数组(Binary Indexed Tree)是又一种静态的树结构。它的首要用途是用于维护前缀和，也即：一数组a[1..n]，随时会改变其中某a[i]，还会询问s[i]=a[1]+a[2]+…+a[i]，树状数组可完美解决这一问题。

定义数组c[0..n]，其中c[i]=a[i-2^k+1]+a[i-a^k+2]+…+a[i]，其中k为i在二进制下末尾0的个数。当我们改变一个a[i]时，会有很多c[i]随之改变；若需查询某个s[i]，需要累加多个c[i]。好在确定需要改变或累加的元素都可以用比较简便的方法得出，这方法的核心就是lowbit值。

定义lowbit(x)=x&(x^(x-1))，它相当于将最右边的1左边的东西全部去掉。若需改变a[i]，则c[i]、c[i+lowbit(i)]、c[i+lowbit(i)+lowbit(i+lowbit(i)]……就是需要改变的c数组中的元素。若需查询s[i]，则c[i]、c[i-lowbit(i)]、c[i-lowbit(i)-lowbit(i-lowbit(i))]……就是需要累加的c数组中的元素。这看上去有些玄妙，我觉得其实也可以不用透彻理解。

一维的树状数组的每个操作的复杂度都是O(logn)的，非常高效。它可以扩充为n维，这样每个操作的复杂度就变成了O((logn)^n)，在n不大的时候仍然完全可以接受。扩充的方法就是将原来改变和查询的函数中的一个循环改成嵌套的n个循环在n维的c数组中操作。

要注意树状树组能处理的是下标为1..n的数组，绝对不能出现下标为0的情况。因为lowbit(0)=0，这样会陷入死循环。对于我这个从来都用C语言思考的家伙来说，这一点格外需要注意。

似乎树状数组也可以用来解决一些与前缀和关联不大的问题，例如NOI2004的cashier，但我还不太会（那题我只会用平衡树或线段树或虚二叉树解）。

示例程序：ural1470.cpp（三维的树状数组）