树状数组
https://oi-wiki.org/ds/fenwick/
管辖区间
右边界：c数组下标i;
左边界：i - lowbit （i）+1;
lowbit（i）表示c[i]区间长度
所以c[i]管辖的区间为 [ i-lowbit(i)+1，i ];
int lowbit(int x){
// x 的二进制中，最低位的 1 以及后面所有 0 组成的数。
// lowbit(0b01011000) == 0b00001000
// ~~~~^~~~
// lowbit(0b01110010) == 0b00000010
// ~~~~~~^~
return x&-x;
}
区间查询
时间复杂度为O（ log（n））
查找区间a[l，r]转化为查询a[1，l-1]和a[1，r]的和，求差。
查询a[1...x]的过程：
· 从c[x]开始往前跳，c[x]管辖有a[x-lowbit(x)+1，x]；
· 令x→x - lowbit(x) ,如果x等于0说明走到了尽头，停止循环；否则回到第一步；
· 将跳到的c合并（可边跳边合并）
int getsum(int x){//a[1]..a[x]的和
int ans=0;
while(x>0){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
树状数组与其他树形态的性质
- 性质一：对于x<=y，要么有c[x]与c[y]相交，要么不相交。
- 性质二：c[x]真包含于c [ x+lowbit(x) ] 。
- 性质三：对于任意x<y<x+lowbit(x)，c[x]与c[y]不相交
事实上，树状数组的树形态是x向x+lowbit(x)连边得到的图，其中x+lowbit(x)是x的父亲
树满足的性质(设fa[u]表示u的直系父亲)：
- u<fa[u]
- u大于u的任何一个后代，小于任何一个祖先
- 点u的lowbit严格小于fa[u]的lowbit
- 我们认为c[1]的高度为0，则点x的高度为log2lowbit（x），即二进制最低位1的位数
- c[u]真包含于c[fa[u]]
- c[u]真包含于c[v]，v是u的任意一个祖先
- c[u]真包含c[v]，v是u的任意一个后代
- 任意u>v，若u不是v的祖先，则c[u]与c[v]不相交
- 任意u>v，若v不是u的后代，则c[u]与c[v]不相交
- 设u=s*2k+1+2k，则其儿子的数量为log2lowbit（u），编号分别为u-2t（0<= t <k）
- u的所有儿子对应c的管辖区间恰好拼接成[u-lowbit(u)+1，u-1]
单点修改
时间复杂度为O（log（n））
只需要修改包含了a[x]的管辖区间
管辖a[x]的c[y]一定包含c[x]，所有y在树状数组树形态上是x的祖先，因此我们从c[x]开始找父亲。
设n表示a的大小，单点修改a[x]的过程：
· 初始令x'=x
· 修改c[x']
· 令x'→x'+lowbit(x')，如果x'>n说明已经跳到了尽头了，停止循环；否则回到第二步
以单点加给出实现：
void add(int x,int k){
while(x<=n){
c[x]+=k;
x+=lowbit(x);
}
}
区间加区间和
知识点：前缀和&差分
该问题使用两个树状数组维护差分数组解决
其中，序列a的差分数组为d，有ai=Σij=1dj
原数组a区间加维护方式：
对于维护差分数组di的树状数组，对l单点加v，r+1单点加-v；
对于维护di*i的树状数组，对l单点加v*l，r+1单点加-v*（r+1）；
int t1[MAXN],t2[MAXN],n;
inline int lowbit(int x){
return x&-x;
}
void add(int k,int v){
int v1=k*v;
while(k<=n){
t1[k]+=v,t2[k]+=v1;
//注意不能写成t2[k]+=k*v,因为k的值已经不是原数组的下标了
k+=lowbit(k);
}
}
int getsum(int *t,int k){
int res=0;
while(k){
res+=t[k];
k-=lowbit(k);
}
return res;
}
void add1(int l,int r,int v){
add(l,v),add(r+1,-v);
}
long long getsum1(int l,int r){
return (r+1ll)*getsum(t1,r)-1ll*l*getsum(t1,l-1)-(getsum(t2,r)-getsum(t2,l-1));
}
单点修改，查询全局第k小
权值数组：b[x]的值为x在a数组中出现的次数
该问题可离散化，如果原序列a的值域过大，可离散化后再建立权值数组b。
对于单点修改，只需将对原数列的单点修改转化为对权值数组的单点修改即可。
具体来说，原数组a[x]从y修改成z，转化为对权值数组b的单点修改就是b[y]单点减1，b[z]单点加1。
二分：时间复杂度是O（log 2n）
对于查询第k小，考虑二分x，查询权值数组中[1,x]的前缀和，找到x0使得[1,x0]的前缀和<k而[1,x0+1]的前缀和>=k，则第k大的数是x0+1。
倍增：时间复杂度是O（log n）
设x=0，sum=0，枚举i从log2n降为0：
· 查询权值数组中[x+1...x+2i]的区间和t
· 如果sum+t<k，扩展成功，x→x+2i，sum→sum+t；否则扩展失败，不操作
这样得到的x是满足[1...x]前缀和<k的最大值，所以最终答案是x+1。
int kth(int k){//对权值树状数组t查询第k小的数,n为数组t长度
int sum=0,x=0;
for(int i=log2(n);~i;--i){
x+=1<<i;
if(x>=n||sum+t[x]>=k)x-=1<<i;
else sum+=t[x];
}
return x+1;
}
Trick
O（n）建树
方法一：
每一个节点的值都是由所有与自己相连的儿子的值求和所得到的，因此每次确定完儿子的值后用自己的值更新自己的直接父亲。
void init(){
for(int i=1;i<=n;++i){
t[i]+=a[i];
int j=i+lowbit(i);
if(j<=n)t[j]+=t[i];
}
}
方法二：
c[i]表示的区间为 [ i - lowbit(i) + 1，i ]，可以先预处理一个sun前缀和数组，用来计算c数组
void init(){
for(int i=1;i<=n;++i){
t[i]=sum[i]-sum[i-lowbit(i)+1];
}
}
标签：单点,树状,int,lowbit,数组,权值,数据结构 From： https://www.cnblogs.com/bible-/p/17112327.html