原理
若$C$数组为树状数组所维护的数组，$A$数组为原数组，则有：
\[C_i=\sum_{j=i-lowbit(i)+1}^{i}{A_j}\]所以求前缀和时就可以直接加完$C_i$后跳到$i-lowbit(i)$，因此把一个前缀和划分成了$O(\log{N})$个区间。
单点改时就可以直接把覆盖到$i$的区间加了就好了，这里运用了一个性质，即$i$后面第一个覆盖到$i$的区间是$i+lowbit(i)$，这才是树状数组妙的地方。
应用
除了基本的单点改，前缀查，着重讲一下值域树状数组求全局第$k$小：
考虑倍增，求出最大的$base$使得$(\sum_{i=1}^{base}{A_i}) < k $，那么$base+1$就是第$k$小。
由于$C_i$管辖$lowbit(i)$长的区间，那么如果我们从大到小枚举每一位$i$，那么当前累计的$base+2^i$管辖的恰好就是最后$2^i$个尝试添加到$base$中的，代码如下（求值域为$[1,n]$中的第$k$小）：
1
2
3
4
5
6
7
8
9
int kth(int k){
int base=0,sum=0;
for(int i=log2(n);~i;i--){
base+=1<<i;// 尝试添加2^i
if(base>=n||sum+C[base]>=k)base-=1<<i;
else sum+=C[base];
}
return base+1;
}
