树状数组

引入：用数组模拟树形结构，可以解决一些区间更新，求和的问题。比线段树更简单一些的数据结构，树状数组能够解决的问题，线段树（~~还没学~~）都可以解决。

原理啥的，我也讲不明白，看大佬博客

构建树状数组

单点更新，区间查询

int n,a[1000010],c[1000010];

int lowbit(int x){
    return x&-x;//返回二进制最后一位1
}

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

int getsum(int i){//求a[1]-a[i]的和
    int ans=0;
    for(;i>0;i-=lowbit(i)) ans+=c[i];
    return ans;
}

来一个模板题

HDU1166

代码：

#include<bits/stdc++.h>
using namespace std;

int n,a[1000010],c[1000010];

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

void updata(int i,int k){
    for(;i<=n;i+=lowbit(i)) c[i]+=k;
}

int getsum(int i){
    int ans=0;
    for(;i>0;i-=lowbit(i)) ans+=c[i];
    return ans;
}


int main(){
    int t;
    cin>>t;
    for(int tot=1;tot<=t;tot++){
        cout<<"Case "<<tot<<":"<<endl;
        memset(a,0,sizeof a);
        memset(c,0,sizeof c);
        cin>>n;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            updata(i,a[i]);
        }
        string s;
        int x,y;
        while(cin>>s&&s[0]!='E'){
            cin>>x>>y;
            if(s[0]=='Q'){
                int sum=getsum(y)-getsum(x-1);
                cout<<sum<<endl;
            }
            else if(s[0]=='S'){
                updata(x,-y);
            }
            else if(s[0]=='A'){
                updata(x,y);
            }
        }
    }

}

~~我的板子好像有问题，以后都不敢用了，TLE一下午不知道咋回事，世界未解之谜，代码还是写简单一些不加乱七八糟的东西，不然debug浪费时间~~
上面这种情况是单点更新、区间查询

单点更新，单点查询

普通数组就可以了。

区间更新、单点查询

给某一段区间同时加上一个数，最后加之后某个点的值，我们知道在某一个区间加上一个数，可以用差分，这里我们用差分数组建立树状数组。

int n,a[1000010],c[1000010];//a原数组，c差分数组

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

void updata(int i,int k){
    for(;i<=n;i+=lowbit(i)) c[i]+=k;
}

int getsum(int i){
    int ans=0;
    for(;i>0;i-=lowbit(i)) ans+=c[i];
    return ans;
}

void add(int l,int r,int k){//在区间[l-r]加上一个数k
    updata(l,k);
    updata(r+1,-k);
}

洛谷P4939

模板题，给你两个操作，0，在给你区间+1，1输出某个点的值。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000010;
int n,a[10000010],c[10000010];//a原数组，c差分数组

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

void updata(int i,int k){
    for(;i<=n;i+=lowbit(i)) c[i]+=k;
}

int getsum(int i){
    int ans=0;
    for(;i>0;i-=lowbit(i)) ans+=c[i];
    return ans;
}

void add(int l,int r,int k){//在区间[l-r]加上一个数k
    updata(l,k);
    updata(r+1,-k);
}

signed main(){
    int m;
    scanf("%lld%lld",&n,&m);
    while(m--){
        int op,l,r;
        scanf("%lld",&op);
        if(op&1){
            scanf("%lld",&l);
            int ans=getsum(l);
            printf("%lld\n",ans);
        }
        else {
            scanf("%lld%lld",&l,&r);
            add(l,r,1);
        }
    }
}

洛谷P5057

跟上一题类似，判断最后的奇偶就行了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000010;
int n,a[10000010],c[10000010];//a原数组，c差分数组

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

void updata(int i,int k){
    for(;i<=n;i+=lowbit(i)) c[i]+=k;
}

int query(int i){
    int ans=0;
    for(;i>0;i-=lowbit(i)) ans+=c[i];
    return ans;
}

void add(int l,int r,int k){//在区间[l-r]加上一个数k
    updata(l,k);
    updata(r+1,-k);
}

signed main(){
    int m;
    scanf("%lld%lld",&n,&m);
    while(m--){
        int op,l,r;
        scanf("%lld",&op);
        if(op==2){
            scanf("%lld",&l);
            int ans=getsum(l)&1;
            printf("%lld\n",ans);
        }
        else {
            scanf("%lld%lld",&l,&r);
            add(l,r,1);
        }
    }
}

区间更新，区间查询

const int N=1000010;
int n,a[1000010],c[1000010];//a原数组，c差分数组
int b1[N],b2[N];
inline int lowbit(int x){return x&-x;}

void updata(int i,int k){
    int tmp=i*k;
    for(;i<=n;i+=lowbit(i)) b1[i]+=k,b2[i]+=tmp;
}

int query(int b[],int i){
    int ans=0;
    for(;i>0;i-=lowbit(i)) ans+=b[i];
    return ans;
}

void add(int l,int r,int k){//在区间[l-r]加上一个数k
    updata(l,k);
    updata(r+1,-k);
}

洛谷P2357

做了这一题发现，区间更新，区间查询也可以用于做单点更新单点查询，区间更新，单点查询。
这一题5个操作，1给区间都加一个数，2给 $a_{1}$ 加上一个数，3给 $a_{1}$ 减一个数，4求一个区间的和，5求 $a_{1}$ 的值。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000010;
int n,a[1000010],c[1000010];//a原数组，c差分数组
int b1[N],b2[N];
inline int lowbit(int x){return x&-x;}

void updata(int i,int k){
    int tmp=i*k;
    for(;i<=n;i+=lowbit(i)) b1[i]+=k,b2[i]+=tmp;
}

int query(int b[],int i){
    int ans=0;
    for(;i>0;i-=lowbit(i)) ans+=b[i];
    return ans;
}

void add(int l,int r,int k){//在区间[l-r]加上一个数k
    updata(l,k);
    updata(r+1,-k);
}

int query(int l,int r){
    return (r+1)*query(b1,r)-query(b2,r)-(l*query(b1,l-1)-query(b2,l-1));
}

signed main(){
    int f;
    cin>>n>>f;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b1[i]+=a[i]-a[i-1];
        b2[i]+=i*(a[i]-a[i-1]);
        int j=i+lowbit(i);
        if(j<=n) b1[j]+=b1[i],b2[j]+=b2[i];
    }
    while(f--){
        int op,l,r,k;
        cin>>op;
        if(op==1){
            cin>>l>>r>>k;
            add(l,r,k);
        }
        else if(op==2){
            cin>>k;
            add(1,1,k);
        }
        else if(op==3){
            cin>>k;
            add(1,1,-k);
        }
        else if(op==4){
            cin>>l>>r;
            int ans=query(l,r);
            cout<<ans<<endl;
        }
        else{
            int ans=query(1,1);
            cout<<ans<<endl;
        }
    }
    return 0;
}

洛谷P1908

求逆序对。

树状数组+离散化

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sc(n) scanf("%lld",&n)
#define SC(a,b) scanf("%lld%lld",&a,&b)
#define pr(a) printf("%lld",a)
const int N=1000010;
int n,a[1000010],c[1000010],b[N];

int lowbit(int x){
    return x&-x;//返回二进制最后一位1
}

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

int getsum(int i){//求a[1]-a[i]的和
    int ans=0;
    for(;i>0;i-=lowbit(i)) ans+=c[i];
    return ans;
}


signed main(){
    sc(n);
    for(int i=1;i<=n;i++) sc(a[i]),b[i]=a[i];//离散化操作
    sort(b+1,b+1+n);
    int cnt=unique(b+1,b+1+n)-(b+1);
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=i-1-getsum(a[i]);
        updata(a[i],1);
    }
    pr(ans);
    return 0;
}

算法专题文章被收录于专栏

怕忘记，好复习