参见： https://www.cnblogs.com/hsd-/p/6139376.html
https://blog.csdn.net/u011644423/article/details/38332287
树状数组(Binary Indexed Tree，BIT，二分索引树)，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题，现多用于高效计算数列的前缀和。它可以以
O(\log n)
\sum_{i=1}^N a[i]
O(\log n)
对某项加一个常数。
用途：主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值。
与线段树的比较：这种数据结构（算法）并没有C++和Java的库支持，需要自己手动实现。在Competitive Programming的竞赛中被广泛的使用。树状数组和线段树很像，但能用树状数组解决的问题，基本上都能用线段树解决，而线段树能解决的树状数组不一定能解决。相比较而言，树状数组效率要高很多。
实际上就是一个二分的原理
图片发自简书App
用到的数组（变量）：
- C[] 树状数组，为A数组中的一段长条的连续和，长条是以它自身为结尾的水平长条。C[]的下标，由i-lowbit(i)+1到i。（i-lowbit（i）+1=长条最左下标）
- lowbit（i） = 2^k，k为i的二进制中0的数量。
- 另外 lowbit(i) = 长条i的长度
- Si，计算query(L,R)=Sr - Sl-1的前缀数组（这里只是逻辑上的数组）
主要原理：
- 1 对于结点i，若为左结点，则父结点为i + lowbit(i); 若为左结点，则父结点为i - lowbit(i) 。对于左结点，它往左爬时（看作特殊根结点）该规律仍成立，右结点亦然。实际上这也是计算前缀数组与修改树状数组的基础。
- 2 计算Si,不一定沿着树地往左往上（参见1与下图）
-
3 修改Ai时，需要更新的C数组，不一定沿着树得往右往上（参见1与下图）
图片发自简书App
int lowbit(int x){
return x&-x;//因为补码
}
void add(int k,int num)
{
while(k<=n)
{
tree[k]+=num;
k+=lowbit(k); //看成右子树
}
}
int read(int k)//1~k的区间和
{
int sum=0;
while(k)
{
sum+=tree[k];
k -=lowbit(k);//看成左子树
}
return sum;
}
void getTree(){
for(int i=1;i<=n;i++){
C[i]=0;//初始化
for(int j=i-lowbit(i)+1;j<=i;j++){
C[i]+=A[j];
}
}
}
