树状数组（BIT）
树状数组不仅仅只有求区间和的作用，还可以以此来查询区间最值或特殊值，（它的查询和插入操作都是O（logn）级别的）；
它的最大好处就是简单易写，实现方便；
定义：
// * 数组大小 #define BITSZ (100) // * 树状数组 int Bit[BITSZ]
单点添加函数：
void AddBit (int k,int val) { while (k<=BITSZ) { Bit[k]+=val; k+=k&-k; } return; }
查询[1,k]的区间和函数：
int QueryBit (int k) { int sum=0; while (k>0) { sum+=Bit[k]; k-=k&-k; } return sum; }
原文：http://www.cnblogs.com/Ztraveler/p/6919996.html