树状数组最核心的部分,便是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];
}

 

Categories:

Tags:

No responses yet

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

近期评论
归档
分类