树状数组模板

单点修改单点查询

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define lowbit(x) x&(-x)
using namespace std;
const int M=200007;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int T,n,sum[2*M];
int upd(int x,int k){
    while(x<=n){
        sum[x]+=k;
        x+=lowbit(x);
    }
}
int p_ans(int x){
    int ans=0;
    while(x){
        ans+=sum[x];
        x-=lowbit(x);
    }
    return ans;
}
char c[25];
int main(){
    int x,k,cnt=0;
    T=read();
    while(T--){
        for(int i=1;i<=n;i++) sum[i]=0;
        cnt++;
        printf("Case %d:\n",cnt);
        n=read();
        for(int i=1;i<=n;i++) x=read(),upd(i,x);
        scanf("%s",c);
        while(c[0]!='E'){
            x=read(); k=read();
            if(c[0]=='A') upd(x,k);
            else if(c[0]=='S') upd(x,-k);
            else printf("%d\n",p_ans(k)-p_ans(x-1));
            scanf("%s",c);
        }
    }
    return 0;
}

View Code

https://www.luogu.org/problem/list?keyword=%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84&page=1

区间加（减）单点查询利用差分实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define lowbit(x) x&(-x)
using namespace std;
const int M=1e6+7;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,m,s[M];
int sum[M];
void upd(int x,int k){
    while(x<=n){
        sum[x]+=k;
        x+=lowbit(x);
    }
}
int p_ans(int x){
    int ans=0;
    while(x){
        ans+=sum[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    int T,l,r,k;
    n=read(); m=read();
    s[0]=0;
    for(int i=1;i<=n;i++) s[i]=read(),upd(i,s[i]-s[i-1]);
    for(int i=1;i<=m;i++){
        T=read();
        if(T==1){
            l=read(); r=read(); k=read();
            upd(l,k);
            upd(r+1,-k);
        }
        else k=read(),printf("%d\n",p_ans(k));
    }
    return 0;
}

View Code

https://vjudge.net/problem/POJ-3468

区间加（减）区间求和依旧利用差分但维护两个树状数组

详情见大佬博客 https://www.cnblogs.com/xenny/p/9739600.html

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define lowbit(x) x&(-x)
#define LL long long
using namespace std;
const int M=2e5+7;
LL read(){
    LL ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,m;
LL s[M],s1[M],s2[M];
void upd(LL x,LL k){
    LL T=x;
    while(x<=n){
        s1[x]+=k;
        s2[x]+=(T-1)*k;
        x+=lowbit(x);
    }
}
LL p_ans(LL x){
    LL T=x,ans=0;
    while(x){
        ans=ans+T*s1[x]-s2[x];
        x-=lowbit(x);
    }
    return ans;
}
char c[20];
int main(){
    n=read(); m=read();
    s[0]=0;
    for(int i=1;i<=n;i++) s[i]=read(),upd(i,s[i]-s[i-1]);
    LL l,r,k;
    for(int i=1;i<=m;i++){
        scanf("%s",c);
        if(c[0]=='C') l=read(),r=read(),k=read(),upd(l,k),upd(r+1,-k);
        else l=read(),r=read(),printf("%lld\n",p_ans(r)-p_ans(l-1));
    }
    return 0;
}

View Code