树状数组模板

文章目录

一、树状数组介绍二、代码

一、树状数组介绍

树状数组是一种用数组模拟的树形结构，修改和查询的复杂度都是O(logN),常用于解决区间更新以及求和问题.

上图中:
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- 2 k 2^k 2k+1]+A[i- 2 k 2^k 2k+2]+…+A[i],其中k为i的二进制中从最低位到高位连续零的长度, 2 k 2^k 2k也叫lowbit,可以利用位运算计算,如下

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

二、代码

树状数组的单点修改,单点查询和区间查询的完整代码如下:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f3f
#define bug(a) cout<<"* "< P;

int n;
int A[N],c[N];//对应原数组和树状数组

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

void updata(int i,int k){ //在i位置加上k
    while(i<=n){
        c[i]+=k;
        i+=lowbit(i);
    }
}

int getsum(int i){  //求前i项的和
    int res=0;
    while(i>0){
        res+=c[i];
        i-=lowbit(i);
    }
    return res;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>A[i];
        updata(i,A[i]);//第i个位置加上A[i]；
    }
    cout< 
区间修改则需要借助差分数组,完整代码如下: 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f3f
#define bug(a) cout<<"* "< P;

int n,m;
ll A[N],c[N];//对应原数组和树状数组

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

void updata(int i,ll k){ //在i位置加上k
    while(i<=n){
        c[i]+=k;
        i+=lowbit(i);
    }
}

ll getsum(int i){  //求d数组前i项的和，也就是A[i]的值
    ll res=0;
    while(i>0){
        res+=c[i];
        i-=lowbit(i);
    }
    return res;
}

int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>A[i];
        updata(i,A[i]-A[i-1]);//第i个位置加上d[i]；
    }
    while(m--){
        char opt;
        cin>>opt;
        if(opt=='Q'){
            int x;
            cin>>x;
            cout<>l>>r>>d;//把区间l~r之间每个元素都加上d
            updata(l,d);
            updata(r+1,-d);
        }
    }
    return 0;
}

树状数组模板

C/C++/C#相关栏目本月热门文章