树状数组笔记

 树状数组，就是这么简单！_哔哩哔哩_bilibili

 c[]是管理数组，也是树状数组

求x的二进制表示下最低位的1及他后面的0构成的值：

lowbit(x)= x&(-x);

1=1 lowbit(1)=1

2=10 lowbit(2)  = 2

3=11 lowbit(3) = 1

4=100 lowbit(4) = 4

5=101 lowbit(5) = 1

6=110 lowbit(6) = 2

7=111 lowbit(7) = 1

8=1000 lowbit(8) = 8

9=1001 lowbit(9) = 1

管理数组c[i] 的区间长度 ：lowbit(i)

c[i]的直接前驱为c[i-lowbit(i)] 即c[i]左侧紧邻的子树的根

c[i]的直接后继为c[i+lowbit(i)] 即c[i]的父节点

c[]的下标从1开始，如果为0则lowbit(0)=0，卡住

计算前缀和：sum[7]=c[7]+c[6]+c[4]                    sum[9]=c[9]+c[8]

对a数组更新：a[i]+k ---> c[5]+k然后c[5]的后继都加k即c[6]+k、c[8]+k

计算区间和：a[i]+a[i+1]+...+a[j] ，即sum[j]-sum[i-1]

int lowbit(int x){//c的区间长度
    return x&(-x);
}

void add(int i , int k){ //点更新 点i加上k
//n为数组长度
    for(;i<=n;i+=lowbit(i))//累加所有后继(父节点)
        c[i]+=k;
}

int sum(int i){//前缀和 a[1]...a[i]
    int ans=0;
    for(;i>0;i-=lowbit(i)) //累加所有前驱
        ans+=c[i];
    return ans;
}

int qjsum(int i , int j){//区间和 ，a[i]+..+a[j]
    return sum(j)-sum(i-1);
}

点更新，从叶子更新到树根，不超过树高O(logn)

前缀和，从节点一直查找前驱，前驱个数不超O(logn)

局限

 

//https://vjudge.net/article/2642

2352 -- Stars 题解Stars_小郑的ac路的博客-CSDN博客