树状数组

xhraiganf · 2026-02-04 01:15:22 · 算法·理论

原理

先看下面这图: 填上数值:

这样我们可以求任意区间的区间和

例: [2:7]=[2:2]+[3:4]+[5:6]+[7:7]

但这样会有冗余, 于是我们把每一行的偶数位删除: 于是删除的位数都可以用减法得到

然后让剩下的每一个区间对应上一个数组的值:

我们发现:

例:

::::success[lowbit的实现] 将x的二进制全部取反+1记为y,再将x & y，就可以得到最后一位 1 的位置

详细请看: https://www.cnblogs.com/fusiwei/p/11752540.html

code:

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

::::

区间查询

根据前缀和的定义，每一个区间和[l,r]都可以由[1,r]-[1,l-1]得来

这样求一个区间就被拆分成两个小过程

然后我们看一些例子(根据图四):

1. [1:7]$可以分为:$[1:4]+[5:6]+[7:7]=c[4]+c[6]+c[7]
2. [1:5]$可以分为:$[1:4]+[5:5]=c[4]+c[5]

看1号例子: c[6] 的 6 是由后面的 c[7] 的 7-lowbit(7) 得来的, c[4] 的 4 是由后面的 c[6] 的 6-lowbit(6) 得来的

结论:

所以,我们就可以从当前x不停往前加,求出[1:x]的值

再用前缀和求出当前区间的值

code:

int query(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
query(r)-query(l-1)//[l:r]的区间值

单点修改

因为每一个区间都是由一个它包含的子区间的和得来

若我们修改一个点的值，那么它所对应的区间的和要改，包含这个区间的区间和也要修改，包含包含这个区间的区间的区间和也要修改(禁止套娃)

例子(根据图四):

修改3号点的值，那么[3:3]、[1:4]、[1:8]也需修改，也就是:c[3]、c[4]、c[8]

观察一下: c[4] 的 4 是由 3+lowbit(3) 得来, c[8] 的 8 是由 4+lowbit(4) 得来

结论:

但: 值最大取到 n，所以循环边界就是 n

code:

void modify(int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}

区间修改

这里需用到差分 ::::success[差分] 详细请见: https://oi-wiki.org/basic/prefix-sum/

是前缀和的逆运算，先需求差分数组(dis) :::align{center}

::: 修改区间[l,r]，就是让 :::align{center}

:::

再求一遍前缀和得到修改过后的原数组

但这样修改虽是O(1)的，但查询却是O(n)的，是一种适用于大量修改、少量查询的算法 ::::

我们让树状数组维护这个差分的过程,每次让[1,l]加上x,让[1,r+1]减去x,于是我们就记录下了区间[l,r]+x的值

code:

void update(int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}
update(l,x);
update(r+1,-x);

单点查询

根据区间修改，我们得知了每个区间的被修改的值

于是我们只需求出包含当前点的区间总和+当前点原来的数值

code:

int query(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
a[x]+query(x)

例题

T1.U438237 ١١(❛ᴗ❛)【树状数组+线段树】-模板（单点修改+区间查询）

这一题模板题,直接套不多讲

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int c[1000010];
int n,q;
int lowbit(int x){
    return (x&(-x));
}
int query(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
void update(int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}
signed main(){
    cin>>n>>q;
    for(int v,i=1;i<=n;i++){
        cin>>v;
        update(i,v); 
    } 
    for(int i=1;i<=q;i++){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){
            update(l,r);//单点修改
        }else{
            cout<<query(r)-query(l-1)<<endl;//区间查询求前缀和
        }
    }
    return 0;
} 

T2.U438249 清点人数

这一题与上题板子的区别有:

• 这一题区间查询只需求[1,m]的区间和
• 有加有减

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int c[1000010];
int n,k;
int lowbit(int x){
    return (x&(-x));
}
int query(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
void update(int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        char op;
        cin>>op;
        if(op=='A'){
            int m;
            cin>>m;
            cout<<query(m)<<endl;//只需求[1,m]的区间和
        }else if(op=='B'){
            int m,p;
            cin>>m>>p;
            update(m,p);//加就是正数
        }else{
            int m,p;
            cin>>m>>p;
            update(m,-p);//减就是负数
        }
    }
    return 0;
} 

T3.P3368 【模板】树状数组 2

此题是区间修改+单点查询的模板，讲解上面有不多讲

code:

#include<bits/stdc++.h>
using namespace std;
int c[500010],a[500010];
int n,m;
int lowbit(int x){
    return (x&(-x));
}
int query(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
void update(int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            int l,r,x;
            cin>>l>>r>>x;
            update(l,x);
            update(r+1,-x);
        }else{
            int x;
            cin>>x;
            cout<<a[x]+query(x)<<"\n";
        }
    }
    return 0;
}

T4.P5057 [CQOI2006] 简单题

这道题也是区间修改+单点查询的题

与上题的区别:

• 这里是异或

所以每次查询时只需看包含这个点的区间的状态求它们异或和

每次修改也是跟上一样，因为一个二进制数异或上两个一还是它本身没有变

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int c[1000010];
int a[1000010];
int n,m;
int lowbit(int x){
    return (x&(-x));
}
int query(int x){
    int ans=0;
    while(x>0){
        ans^=c[x];
        x-=lowbit(x);
    }
    return ans;
}
void update(int x,int v){
    while(x<=n){
        c[x]^=v;
        x+=lowbit(x);
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            int l,r;
            cin>>l>>r;
            update(l,1);
            update(r+1,1);
        }else{
            int x;
            cin>>x;
            cout<<query(x)<<endl;
        }
    }
    return 0;
} 

离散化

因下几题需离散化，所以来讲一下

离散化，本质上是一种哈希，它在哈希后依然能保证顺序不变

它适用于数字很大，但只看相对大小的问题

于是我们可以按顺序给它们编号

离散化分两种:

1. 相同的值有不同的编号(一般按出现顺序编号)
2. 相同的值是相同的编号

再编号

所以用代码模拟以上过程即可

T1.U523499 ١١(❛ᴗ❛)【离散化】-并列大小

这道题属于第2种离散化

每一个相同的值都要编号成相同的号码

做法:

1. 先复制一份原数组
2. 将复制数组从小到大排序
3. 将复制数组去重
4. 二分查找原数组再复制数组中的位置也就是编号，它就是离散化后的值

code:

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int tmp[100010];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        tmp[i]=a[i];//复制数组
    }
    sort(tmp+1,tmp+1+n);//排序
    int cnt=unique(tmp+1,tmp+1+n)-tmp-1;//去重
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(tmp+1,tmp+1+cnt,a[i])-tmp;//查找位置
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

T2.U523492 ١١(❛ᴗ❛)【离散化】-非并列排名

这道题属于第1种离散化

每一个相同的值都要编号成不同的号码

做法:

1. 拿一个结构体装它的数值和位置
2. 排序，若值不同按值从大到小排序，若值相同按位置从小到大排序
3. 将离散化后的数字放回原数组

code:

#include<bits/stdc++.h>
using namespace std;
struct node{
    int v,id;
};
node a[100010];
int pos[100010];
bool cmp(node x,node y){
    if(x.v!=y.v)return x.v>y.v;//值不同按值从大到小排序
    return x.id<y.id;值相同按位置从小到大排序
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].v;//记录值
        a[i].id=i;//记录位置
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        pos[a[i].id]=i;//将离散化的数装回去
    }
    for(int i=1;i<=n;i++){
        cout<<pos[i]<<" ";
    }
    return 0;
}

值域树状数组

T5.U438285 ١١(❛ᴗ❛)【树状数组】-数星星 Stars

先看输入，此题x,y是按y坐标增序给出，y 坐标相同的按x坐标增序给出

所以只要在当前点的左边且x_i \ge x_j这样它就可以升上一级

我们让大的数为一个区间，它下面包含许多小于等于它的数

所以当小于等于它的数来了一个后，它的数值也会+1

code:

#include<bits/stdc++.h>
using namespace std;
int c[32010];
int ans[32010];
struct node{
    int x,y;
}a[32010];
int n;
int lowbit(int x){
    return (x&(-x));
}
int query(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void update(int x,int v){
    while(x<=32001){//不是枚举到n
        c[x]+=v;
        x+=lowbit(x);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        a[i].x++;//避免从0开始
    }
    for(int i=1;i<=n;i++){
        ans[query(a[i].x)]++;//查询当前星星的等级并计数
        update(a[i].x,1);//将当前星星加入树状数组
    }
    for(int i=0;i<n;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}

T6.P1908 逆序对

这道题我们注意到，每个数字的值很大且只要比较它们的相对大小，所以要使用离散化

然后这道题看逆序对也就是找i>j且a_i<a_j的点

所以用值域树状数组来维护.

code:

#include<bits/stdc++.h>
using namespace std;
int c[500010],a[500010],tmp[500010];
int n,cnt;
int lowbit(int x){
    return (x&(-x));
}
int query(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
void update(int x,int v){
    while(x<500010){
        c[x]+=v;
        x+=lowbit(x);
    }
}
void lsh(){
    sort(tmp+1,tmp+1+n);
    int cnt=unique(tmp+1,tmp+1+n)-tmp-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(tmp+1,tmp+1+cnt,a[i])-tmp;
        a[i]=cnt-a[i]+1;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        tmp[i]=a[i];
    }
    lsh();
    long long ans=0;
    for(int i=1;i<=n;i++){
        ans+=query(a[i]-1);
        update(a[i],1);
    }
    cout<<ans;
    return 0;
}