简述
什么是树状数组呢，顾名思义就是树一样的数组，本质就是用数组模拟树形结构。
树状数组有什么用呢，树状数组可以实现单点更新，单点查询，区间查询和区间更新，维护的东西和线段树可以类比的，就是满足区间加法性质的属性，例如最值，和，gcd等。
树状数组可以干的东西线段树也能干，但线段树干的东西树状数组不一定能干。树状数组的复杂度和线段树同级，但常数更低且代码量更为简答，所以我们能用树状数组就用树状数组，这样就不容易TLE了。
lowbit操作
首先我们来了解一个操作，lowbit(x)，这个操作取出x二进制最低位的1，例：lowbit(10100)=100
ll lowbit(ll x){
return x&(-x);
}
为什么是x&(-x)呢？我们知道对一个数取负就是对这个数取反加一。我们设原数的二进制为xxx1000…，该数取反为yyy0111…，令其加一，我们可以发现，取反加一后的数只有一位是1，且该位置就是原数最低位的1，所以我们令x&(-x)就可以得到x的lowbit了。
树的样子
底下的代表我们输入的a数组，上面的代表我们的树状数组c数组。从空间上来说，树状数组只需要存二叉树的根和左子树就行，因为右子树可以由根减左子树获得，则有：
•C[1] = A[1];
•C[2] = A[1] + A[2];
•C[3] = A[3];
•C[4] = A[1] + A[2] + A[3] + A[4];
•C[5] = A[5];
•C[6] = A[5] + A[6];
•C[7] = A[7];
•C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];
可以发现，这颗树是有规律的，我们可以发现，C[i]存了lowbit(i)个的和。
单点更新，区间求和
单点更新
例如我们需要令a[1]+=k，则需要维护c1，c2，c4，c8这些包含a1的节点，我们可以发现这些需要维护的节点是层次关系：c1
区间求和
例如我们需要查询区间3到5的和，其值等于a3+a4+a5，如果我们得到前缀和sum[i]，其值就等于sum[5]-sum[2]，而树状数组恰恰就是利用了前缀和求出区间和。
例如我们要求sum(7)，那么sum(7)=c[7]+c[6]+c[4]，我们可以很容易看出，6是由7-lowbit(7)得到的，4是由6-lowbit(6)得到的，而4减它的lowbit就等于0了。我们可以知道，sum(i)可由每个c位置的贡献求出，每个位置为上个位置减lowbit。为什么可以这样呢，我们来看i=2的幂时，这时c[i]就完全包含1到i这i个元素，无需做任何处理，当i不是2的幂时，需要一个一个处理，直到i消掉低位的1变为2的幂，例如i=7的时候，一开始lowbit(7)=1，也就是说c[7]只维护了一个节点那就是a[7]，令其减loewbit，得i=6，此时c6维护了a5和a6两个节点，减去lowbit得i=4，包含1到i所有节点，故加上贡献后结束。
所以下一个有贡献的位置是当前位减lowbit(当前)。
构建
此时c数组就是这个树状数组了，c[x]保存的是从下标x开始 a[x]+a[x-1]+a[x-2]+a[x-k] ，至于有几个a[]相加，这里有一个计算方法，把x化为二进制，从右向左找到第一个1的位置，这个位置所代表的十进制的数字k就意味着c[x]=a[x]+a[x-1]+a[x-2]+…+a[x-k-1];
void build(){
for (int i=1; i=i-lowbit(i)+1; j--)
c[i]+=a[j];
}
void update(int x,int val,int n){
//x位置的值加上val,n为总叶子个数
for(int i=x;i=1;i-=lowbit(i)){
ans1+=c[i];
}
return ans1;
}
ll sum(int x,int y){//区间查询
return sum(y)-sum(x-1);
}
区间更新，单点求值
如果单纯的对原数组的树状数组进行区间求和，不难看出这是一件复杂度爆炸的事情；所以我们不妨对原数组求其差分数组，然后对差分数组建立树状数组，那么区间修改就变为了对差分数组的(左右端点的两次单点修改)，是不是就快多了呢？
同样，单点查询就可以看作是对差分数组的区间求和，这样又转换成了最基本的树状数组操作问题。
void build(){
for(int i=1;i>a[i];
b[i]=a[i]-a[i-1]; //b是差分数组，求b的树状数组可以将区间修改变为两次单点修改，将单点查询改为一次区间求和
c[i]=b[i];
for(int j=i-lowbit(i)+1;j
void update(int x,int y,int k){//区间[x,y]加上k
for(int j=x;j0;j-=lowbit(j)){ //区间求和，将区间拆分成多个区间的和
ans+=tree[j];
}
return ans;
}
模版
#include
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
ll lowbit(ll x){
return x&(-x);
}
void update(int x,int val,int n){
for(int i=x;i=1;i-=lowbit(i)){
ans1+=c[i];
}
return ans1;
}
ll sum(int x,int y){
return sum(y)-sum(x-1);
}
void build(){
for (int i=1; i=i-lowbit(i)+1; j--)
c[i]+=a[j];
}
int main()
{
return 0;
}
7.28已更新
Original: https://www.cnblogs.com/aska00/p/16524229.html
Author: Aska0
Title: 树状数组
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/685951/
转载文章受原作者版权保护。转载请注明原作者出处！