树状数组最核心的部分,便是lowbit()
int lowbit(int x){return x ^ (-x);}
它的作用是返回x在二进制下最低位的1所对应的值
即计算2^k的值
在树状数组中,它恰好返回当前节点所指的下一个中继节点(即存储区间和的节点)
还有一个重要的问题,查询与修改时,方向不能错
int query(int loc){//查询向下查询
long long ans=0;
for(int i=loc;i>0;i-=lowbit(i)){
ans+=C[i];
}
retrun ans;
}
void add(int loc,int x){//修改则是对它后继的中继节点有影响,向上更新
for(int i=loc;i<=n;i+=lowbit(i)){
C[i]+=x;
}
}
最后是建树。设C[i]为树状数组中的第i项,A[i]存储原序列的第i项
则有C[i] = A(i – 2^k + 1) + … + A[i]
void build(){
for(int i=1;i<=n;i++)//枚举C[i]
for(int j=i-lowbit(i)+1;j<=i;j++)//从i-2^k+1累加到i
C[i]+=A[j];
}
No responses yet