树状数组

一维树状数组

单点修改，区间查询

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '
'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;

#define int long long
int n;

const int maxn=1e6+10;
int d[maxn];
inline int lowbit(int x){return -x&x;}

void add(int x,int y){
    while(x<=n){
        d[x]+=y;x+=lowbit(x);
    }
}

int get_sum(int x){
    int res=0;
    while(x){
        res+=d[x];x-=lowbit(x);
    }
    return res;
}

signed main(){
    int q;cin>>n>>q;
    for(int i=1;i<=n;++i){
        int t;cin>>t;
        add(i,t);
    }
    while(q--){
        int p,x,y;cin>>p>>x>>y;
        if(p==1){
            add(x,y);
        }else{
            cout<<(get_sum(y)-get_sum(x-1))<<endl;
        }


    }
}

区间修改，单点查询

https://loj.ac/problem/131

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '
'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;

#define int long long
int n;
const int maxn=1e6+10;
int d[maxn],cha[maxn];
inline int lowbit(int x){return -x&x;}


void add(int x,int y){
    while(x<=n){
        d[x]+=y;x+=lowbit(x);
    }
}

int get_sum(int x){
    int res=0;
    while(x){
        res+=d[x];x-=lowbit(x);
    }
    return res;
}

signed main(){
    int q;cin>>n>>q;
    for(int i=1;i<=n;++i){
        cin>>cha[i];
        add(i,cha[i]-cha[i-1]);
    }
    while(q--){
        int op;cin>>op;
        if(op==1){
            int l,r,x;cin>>l>>r>>x;
            add(l,x);
            add(r+1,-x);
        }else{
            int i;cin>>i;
            cout<<get_sum(i)<<endl;

        }
    }

}

区间修改，区间查询

https://loj.ac/problem/132

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '
'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;

#define int long long
int n;
const int maxn=1e6+10;
int t[maxn];
inline int lowbit(int x){return -x&x;}

class Tree_arry{

public:
    int d[maxn];
    void add(int x,int y){
        while(x<=n){
            d[x]+=y;x+=lowbit(x);
        }
    }

    int query(int x){
        int res=0;
        while(x){
            res+=d[x];x-=lowbit(x);
        }
        return res;
    }
}b,bi;

int get_xum(int x){
    int res=0;
    res=(x+1)*b.query(x)-bi.query(x);
    return res;

}

signed main(){
    int q;cin>>n>>q;
    for(int i=1;i<=n;++i){
        cin>>t[i];
        b.add(i,t[i]-t[i-1]);
        bi.add(i,i*(t[i]-t[i-1]));
    }
    while(q--){
        int op;cin>>op;
        int l,r,x;cin>>l>>r;
        if(op==1){
            cin>>x;
            b.add(l,x);
            b.add(r+1,-x);
            bi.add(l,x*l);
            bi.add(r+1,-x*(r+1));
        }else{
            cout<<(get_xum(r)-get_xum(l-1))<<endl;

        }
    }

}

二维树状数组

单点修改，区间查询

https://loj.ac/submission/868327

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '
'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;

#define int long long
int n,m;
const int maxn=1e6+10;
const int MAXN=(1<<12)+10;

int d[MAXN][MAXN];
inline int lowbit(int x){return -x&x;}

void add(int x,int y,int val){

    while(x<=n){
        int ty=y;
        while(ty<=m){
            d[x][ty]+=val;ty+=lowbit(ty);
        }
        x+=lowbit(x);
    }


}

int query(int x,int y){
    int res=0;
    while(x){
        int ty=y;
        while(ty){
            res+=d[x][ty];
            ty-=lowbit(ty);
        }
        x-=lowbit(x);
    }
    return res;

}

int get_xum(int a,int b,int c,int d){
    return query(c,d)-query(c,b-1)-query(a-1,d)+query(a-1,b-1);

}

signed main(){
    cin>>n>>m;
    int op,a,b,c,d,k;
    while(cin>>op){
        if(op==1){
            cin>>a>>b>>k;
            add(a,b,k);
        }else{
            cin>>a>>b>>c>>d;
            cout<<get_xum(a,b,c,d)<<endl;
        }
    }

}

区间修改，单点查询

https://loj.ac/problem/134

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '
'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;

#define int long long
int n,m;
const int maxn=1e6+10;
const int MAXN=(1<<12)+10;

int d[MAXN][MAXN];
inline int lowbit(int x){return -x&x;}

void add(int x,int y,int val){

    while(x<=n){
        int ty=y;
        while(ty<=m){
            d[x][ty]+=val;ty+=lowbit(ty);
        }
        x+=lowbit(x);
    }


}

int query(int x,int y){
    int res=0;
    while(x){
        int ty=y;
        while(ty){
            res+=d[x][ty];
            ty-=lowbit(ty);
        }
        x-=lowbit(x);
    }
    return res;

}

void update_add(int a,int b,int c,int d,int k){
    add(a,b,k);
    add(a,d+1,-k);
    add(c+1,b,-k);
    add(c+1,d+1,k);
}

signed main(){
    cin>>n>>m;
    int op,a,b,c,d,k;
    while(cin>>op>>a>>b){

        if(op==1){
            cin>>c>>d>>k;
            update_add(a,b,c,d,k);
        }else{
            cout<<query(a,b)<<endl;
        }
    }

}

区间修改，区间查询

https://loj.ac/problem/135

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '
'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;

#define int long long
int n,m;
const int maxn=1e6+10;

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

class Tree_arry{

public:
    int d[3000][3000];

    void add(int x,int y,int val){
        while(x<=n){
            int ty=y;
            while(ty<=m){
                d[x][ty]+=val;ty+=lowbit(ty);
            }
            x+=lowbit(x);
        }
    }

    int query(int x,int y){
        int res=0;
        while(x){
            int ty=y;
            while(ty){
                res+=d[x][ty];
                ty-=lowbit(ty);
            }
            x-=lowbit(x);
        }
    return res;
    }

}b,bi,bj,bij;



void add_all(int x,int y,int val){
    b.add(x,y,val);
    bi.add(x,y,val*x);
    bj.add(x,y,val*y);
    bij.add(x,y,val*x*y);
}

void update_add(int x1,int y1,int x2,int y2,int k){
    add_all(x1,y1,k);
    add_all(x2+1,y2+1,k);
    add_all(x2+1,y1,-k);
    add_all(x1,y2+1,-k);
}

int get_xum(int x,int y){
    return (x+1)*(y+1)*b.query(x,y)-(y+1)*bi.query(x,y)-(x+1)*bj.query(x,y)+bij.query(x,y);

}

int get_sum(int x1,int y1,int x2,int y2){
    return get_xum(x2,y2)-get_xum(x2,y1-1)-get_xum(x1-1,y2)+get_xum(x1-1,y1-1);
}
signed main(){
    cin>>n>>m;
    int op,x1,y1,x2,y2,d;
    while(cin>>op){
        cin>>x1>>y1>>x2>>y2;
        if(op==1){
            cin>>d;
            update_add(x1,y1,x2,y2,d);
        }else{
            cout<<get_sum(x1,y1,x2,y2)<<endl;

        }
    }

}