树状数组 note

userId_undefined
请‎输‎入‎文‎本‎. ‎🐛‎
出道萌新分支·分支解题者I/O·IO入门者

2026-08-31 21:15:51

发布于：上海

40阅读
0回复
0点赞

前置芝士：前缀和
当然先是来复习一下前缀和：
前缀和，用 O(1)O(1) 的时间复杂度来求前若干个数的和或从第 ll 个数到第 rr 个数的和（s[r]-s[l-1）

前缀和 VS 数组
像素方块的硬核才是王道，你那卡通画风根本没技巧；萌趣的世界才受大家喜欢，你那硬核玩法早就被时代落败
前缀和：求和 O(1)O(1) ，修改 O(n)O(n)
数组：修改 O(1)O(1) ，求和 O(n)O(n)
显然可以注意到各有优劣，那么如何平衡一下呢？
树状数组君登场！
它既能修改又能求和，并且平衡了前缀和和数组的时间复杂度

在学树状数组前，要先理解一下一个数学概念：LowBit

  • 一个数的 LowBit 值为这个数的二进制从低位开始第一个 1 和后面所有 0 组成的 2k2^k （kk 为最低位 1 所在位数）

举板栗：

原数 二进制形式 LowBit 值
15 1111 1(1)
26 11010 10(2)
128 10000000 10000000(128)

如何去求一个数的 LowBit 值呢？
循环、暴力枚举？
当然拉完了，不如 x&(-x)
不懂就要问，为啥？
下面以 x=40(1010002)x=40(101000_2) 为例分析
int 应为 4 字节 32 位，这里简化为 8 位处理
即：x=00101000x=00101000
−x-x 源码：1010100010101000 ，−x-x 反码为除符号位均取反，即 1101011111010111 ，−x-x 补码进行加一操作，变为 1101100011011000
看我超级按位与
-- 0010100000101000（前面两个用来占位对齐的（））
& 1101100011011000
——————
-- 0000100000001000
得到这个数的 LowBit 值

好的哺乳蒸屉
对于下标 xx ，树状数组存的是从第 xx 个数开始前 LowBit(x) 的值
以 x=40x=40 为例分析，LowBit(x) 值为 1000
f[40] = a[40]+ a[39]+ a[38]+ a[37]+ a[36]+ a[35]+ a[34]+ a[33]
101000,101000,100111,100110,100101,100100,100011,100010,100001
LowBit 位前：保持不变
LowBit 位：1 改为 0
LowBit 位后：除全 0 的所有情况

懒得打字了自己看吧

求 LowBit 值函数：

int lowbit(int x){
    return x&(-x);
}

修改元素代码：

void ADD(int p,int k){
    while(p<=n)f[p]+=k,p+=lowbit(p);
}

时间复杂度 O(log⁡n)O(\log n)

如何求原数组中前 x 个数的和
假设我们求前 13 个数的和
看图

栈里那些极度谦虚自己为区的实际上还没我区的和理解能力正常的应该都能看懂
求区间和代码：

int SUM(int p){
    int sum=0;
    while(p>0){
        sum+=f[p],p-=lowbit(p);
    }return sum;
}

时间复杂度 O(log⁡n)O(\log n)

看题
P3374 一眼君好久没出现了

namespace HQ{
    using ll=long long;
    void init(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);}
    inline ll read(){ll num=0,sign=1,ch;while((ch=getchar())==' ' or ch=='\n' or ch=='\t'){}if(ch=='-'){sign=-1;ch=getchar();}else if(ch=='+')ch=getchar();while(ch>='0' and ch<='9'){num=num*10+(ch-'0');ch=getchar();}return sign*num;}
    inline void write(ll n){if(n<0){putchar('-');n*=-1;}if(n>=10){write(n/10);}putchar(n%10+'0');}
    int n,m;
    long long f[510000];
    int lowbit(int x){
        return x&(-x);
    }void ADD(int p,int k){
        while(p<=n)f[p]+=k,p+=lowbit(p);
    }int SUM(int p){
        int sum=0;
        while(p>0){
            sum+=f[p],p-=lowbit(p);
        }return sum;
    }
    void Main(){
        init();
        cin>>n>>m;
        for(int i=1;i<=n;++i){
            int x;
            cin>>x;
            ADD(i,x);
        }for(int i=1;i<=m;++i){
            int op,x,y;
            cin>>op>>x>>y;
            if(op==1){
                ADD(x,y);
            }else cout<<SUM(y)-SUM(x-1)<<'\n';
        }
        return;
    }
}

P10589 有点难啊 QWQ

namespace HQ{
    using ll=long long;
    void init(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);}
    inline ll read(){ll num=0,sign=1,ch;while((ch=getchar())==' ' or ch=='\n' or ch=='\t'){}if(ch=='-'){sign=-1;ch=getchar();}else if(ch=='+')ch=getchar();while(ch>='0' and ch<='9'){num=num*10+(ch-'0');ch=getchar();}return sign*num;}
    inline void write(ll n){if(n<0){putchar('-');n*=-1;}if(n>=10){write(n/10);}putchar(n%10+'0');}
    ll n,m;
    ll f[510000];
    ll l[210000][2],r[210000][2];
    ll lowbit(ll x){
        return x&(-x);
    }void ADD(ll p){
        while(p<=n)f[p]++,p+=lowbit(p);
    }ll SUM(ll p){
        ll sum=0;
        while(p>0){
            sum+=f[p],p-=lowbit(p);
        }return sum;
    }
    void Main(){
        init();
        cin>>n;
        ll a[210000];
        for(int i=1;i<=n;++i){
            cin>>a[i];
        }for(int i=1;i<=n;++i){
            l[i][0]=i-1-SUM(a[i]);
            l[i][1]=SUM(a[i]-1);
            ADD(a[i]);
        }memset(f,0,sizeof f);
        for(int i=n;i>=1;--i){
            r[i][0]=n-i-SUM(a[i]);
            r[i][1]=SUM(a[i]-1);
            ADD(a[i]);
        }ll ans1=0,ans2=0;
        for(int i=1;i<=n;++i){
            ans1+=l[i][0]*r[i][0],ans2+=l[i][1]*r[i][1];
        }cout<<ans1<<' '<<ans2;
        return;
    }
}

也不知树状数组会有啥用

userId_undefined
去预览
0/2000

全部评论 4

热门讨论