树状数组——学习笔记

大佬blog

前置知识

前缀和

关于数组a

s[i]=s[i-1]+a[i]

差分(区间修改)

e.g 对于集合A = { x , y , z , w , u , v }，将y,z和w分别加上a，求操作后数组.

集合C = { x , y-x , z-y , w-z , u-w , v-u } //这叫差分

集合C‘ = { x , y-x+a , z-y , w-z , u-w-a , v-u }

集合ANS = { x , y+a , z+a , w+a , u , v } //求前缀和

原理

红：C[i] 代表树状数组

黑：A[i] 代表普通数组

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] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i]; //k为i的二进制中从最低位到高位连续零的长度

怎么求呢？

lowbit( x )

引入一个新函数——lowbit( x )

指一个二进制数从低位到高位第一个非零数连上后面的零所组成的另一个二进制数

e.g 4(10)=100(2)

lowbit(4)=4

7(10)=111(2)

lowbit(7)=1

12(10)=1100(2)

lowbit(12)=4

位运算实现：lowbit( i ) = i & ( -i )

回来

树状数组中下标为i的点维护的是线段树下标为[i-lowbit(i)+1,i]这个区间数值的和

好der

操作

前缀查询

拆分

#define lowbit(x) x&(-x)
int query(int s[],int node){
    int sum = 0;
    while(node){
        sum += s[node];
        node -= lowbit(node);
    }
    return sum;
}

单点修改

#define lowbit(x) x&(-x)
void update(int s[],int x,int val){
    while(x<=n){
        s[x] += val;
        x += lowbit(x);
    }
    return;
}

题

P3374

P3368（用到了差分测试数据模拟一下就清楚了）

LOJ#132（绝了，过不去）大佬blog（主要看推导）

P3431（不会算了）