1. 简介
定义问题如下：我们有n个盒子，可能的操作为：
往第i个盒子增加石子(对应下文的update函数)
计算第k个盒子到第l个盒子的石子数量(包含第k个和第l个)
原始的解决方案中(即用普通的数组进行存储，box[i]存储第i个盒子装的石子数)， 操作1和操作2的时间复杂度分别是O(1)和O(n)。假如我们进行m次操作，最坏情况下， 即全为第2种操作，时间复杂度为O(n*m)。使用某些数据结构(如
) ，最坏情况下的时间复杂度仅为O(m log n)，比使用普通数组为快许多。 另一种方法是使用数状数组，它在最坏情况下的时间复杂度也为O(m log n)，但比起RMQ， 它更容易编程实现，并且所需内存空间更少。
2. 符号定义
BIT: 树状数组
MaxVal: 具有非0频率值的数组最大索引，其实就是问题规模或数组大小n
f[i]: index为i的频率值，即原始数组中第i个值。i=1…MaxVal
c[i]: index为i的累积频率值，c[i]=f[1]+f[2]+…+f[I]
tree[i]: index为i的BIT值(下文会介绍它的定义)
num^- : 整数num的补，即在num的二进制表示中，0换为1，1换成0。如：num=10101，则 num^- =01010
注意
: 一般情况下，我们令f[0]=c[0]=tree[0]=0，所以各数组的索引都从１开始。 这样会给编程带来许多方便。
3. 基本思想
1.png
2.png
a get parent(for sum)
求a的补码b
i-=(i&-i)a get next(for update)
求a的补码b
i+=(i&-i)
