学习原因：正常的数组更新数组中一个区间的值的时间复杂度是O（n），树状数组则将一个数组转化成一个树形结构，这样每次更新的时间复杂度是O（log（n）），时间复杂度大大降低
模板：
/** 求2的次方 */ int lowbit(int t) { return t&(-t); } /** 求前n项和 sum(x)=A[1]+A[2]+ ...+A[x] A[i] + A[i+1] + … + A[j] = sum(j)-sum(i-1) */ int sum(int x) { int sum=0; while(x>0) { sum+=in[x]; x-=lowbit(x); } return sum; } /** 更新某个元素的大小 A[pos]+=num */ void add(int pos,int num) { while(pos<=n) { in[pos]+=num; pos+=lowbit(pos); } }原文链接：http://dongxicheng.org/structure/binary_indexed_tree/
转载于:https://www.cnblogs.com/gaoss/p/4973281.html
相关资源：树状数组算法的描述和代码的实现