树状数组可以很方便地实现数组的动态修改求和，并且代码量非常小！经过拓展之后，还可以实现区间修改单点查询、求区间最值和第 K 大值（继续学习之后再更新）
基本功能的实现主要有三个函数，lowbit 、 add 、 getsum；
1 int lowbit(int x){return x&(-x);}
2 //lowbit函数，决定下一个/上一个覆盖区间
3
4 void add(int x,int a){
5 for(int i=x;i<=N;i+=lowbit(i))c[i]+=a;
6 }
7 //单点加数
8
9 int sum(int x){
10 int ans=0;
11 for(int i=x;i>0;i-=lowbit(i))ans+=c[i];
12 return ans;
13 }
14 //区间求和
原文：http://www.cnblogs.com/cenariusxz/p/4366714.html