树状数组（二叉索引树）的理解

二叉索引树，Binary Indexed Tree（BIT），在结构上是一个数组a[1],a[2],a[3],...。

BIT的关键概念是数组的每个元素其实代表了从自己向前（左）延申的一段区间。

具体来说，a[x]代表了区间(x-lowbit(x),x]（注意左开右闭），下文中称这个区间为a[x]的代表区间。

神奇之处是，任意从1开始的区间(0,x]都可以划分成少量几个“代表区间”。第一个“代表区间”是a[x]所代表的，长度为lowbit(x)的区间(x−lowbit(x),x]，第二个区间是a[t],t=x−lowbit(x)所代表的长度为lowbit(t)的区间(t−lowbit(t),t]，第三个、第四个区间以此类推。事实上，x的二进制表示中每个“1”都对应了一个“代表区间”。

这些“代表区间”有一个性质，任意两个“代表区间”要么完全不重合，要么一个完全包含另一个，不可能部分重合。你任意取一个“代表区间”，然后你在它内部任取一个位置，考察这个位置的“代表区间”，从lowbit的角度考察就会发现，后者的左端点不可能比前者的左端点更小。

还有一个性质，对于a[x]的代表区间seg(x)来说，我们想找一个a[y]，使seg(y)完全包含seg(x)且y尽可能接近x，那么可以通过公式：y=x+lowbit(x)。我们可以分别从充分性、必要性证明这个公式是正确的。首先，lowbit(y)至少是2倍的lowbit(x)，所以seg(y)一定能够包含seg(x)。其次，任何介于x与y之间的位置t，seg(t)都一定不与seg(x)重合。这主要是因为：若t=x+d,d<lowbit(x)，那么就一定有lowbit(t)<=d。

所以我们可以用这个公式从1个小区间开始找出一连串相互包含的区间，这也是BIT进行单点修改的依据。