一. 概述
树状数组是一种支持数组的单点修改，以及求前缀和（区间求和）的一种简单数据结构，作为线段树的下位替代
简单来说，树状数组就是利用lowbit（二进制化最后一位表示的值）的性质，把n个节点串起来，隐式地构造一棵树
每个节点x的父亲是x+lowbit(x)，当前x节点左边最大的节点是x-lowbit(x)
正常来说单点修改时间复杂度为O(1),求区间和时间复杂度为O(n)
使用前缀和的时候单点修改O(n)，区间求和O(1)
树状数组属于一种折中的方法，实际上是利用lowbit和二进制位的性质实现的一种简易区间划分（相比线段树）
二. C++做题模板
vector<int> tree;
int lowbit(int x){//求二进制化最后一位的值
return x&(-x);
}
void updata(int i,int k){ //在i位置加上k，O(logn)复杂度单点修改
while(i<=n){//更新子树上所有值
tree[i]+=k;
i+=lowbit(i);//移动到父亲节点
}
}
long long getsum(int i){ //求数组前i项的和
long long res=0;
while(i>0){//O(logn)求前缀和
res+=tree[i];
i-=lowbit(i);//移动到前一棵子树（子区间）
}
return res;
}