声明：全部代码未经编译，不保证正确性，仅限逻辑学习，请勿直接抄袭
什么是树状数组
树状数组，本质是运用二进制运算规则维护区间。它的效率高于线段树，空间也少于线段树。但是所能维护的数据操作比较单一。
lowbit函数
lowbit(x)，作用是得到 \(x\) 的二进制最低位1表示的十进制数。
写法如下：
int lowbit(int x){
return x-(x&(x-1));
}
或
int lowbit(int x){
return x&-x;
}
为何如此，自己推一下就行了。
树状数组构建
严格来说树状数组不需提前构建，它只有一个add(x,k)函数，用于在数组x位置加上或更改为k。
设原数组a[n]，树状数组tree[n]，则tree[i]代表在原数组位置 \(i\) 开始，向前数lowbit(i)个数（包括第 \(i\) 个数）的和。
单点修改代码：
void add(int x,int k){
while(x<=n){
tree[x]+=k;
x+=lowbit(x);
}
}
树状数组区间求和
由于树状数组维护的是部分前缀和，所以很简单。
代码：
int sum(int x){
int ans=0;
while(x>=1){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
//区间[l,r]的和就是sum(r)-sum(l-1);
树状数组区间修改
这里用到了差分的思想。
原数列：0 0 0 0 0
我们要给2-4那一段加上x，可以这样操作：
0 x 0 0 -x
然后进行单点查询时加上原数组中的数就行了。