P3368 【模板】树状数组 2

· · 个人记录

线段树 tzt模板，区间修改，单点查询，懒惰标记

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct tree {
    int lc,rc,sum,tag;
} a[1000005];
int n,m,t,ans,A[500005],x,y,w,q;
void pushup(int u) {
    a[u].sum=a[a[u].lc].sum+a[a[u].rc].sum;
}
void pushdown(int u,int l,int r) {
    int mid=(l+r)/2;
    a[a[u].lc].sum+=(mid-l+1)*a[u].tag;
    a[a[u].lc].tag+=a[u].tag;
    a[a[u].rc].sum+=(r-mid)*a[u].tag;
    a[a[u].rc].tag+=a[u].tag;
    a[u].tag=0;
}
void build(int u,int l,int r) {
    if(l==r) {
        a[u].sum=A[l];
        return;
    }
    int mid=(l+r)/2;
    a[u].lc=++t;
    build(a[u].lc,l,mid);
    a[u].rc=++t;
    build(a[u].rc,mid+1,r);
    pushup(u);
}
void update(int u,int l,int r,int ll,int rr,int w) {//区间更新 
    if(ll<=l&&r<=rr) {
        a[u].sum+=(r-l+1)*w;
        a[u].tag+=w;
        return;
    }
    int mid=(l+r)/2;
    pushdown(u,l,r);//只要往下走，就把懒惰标记捎下去
    if(ll<=mid)update(a[u].lc,l,mid,ll,rr,w);
    if(rr>mid)update(a[u].rc,mid+1,r,ll,rr,w);
    pushup(u);
}
int query(int u,int l,int r,int ll,int rr) {//区间查询 
    int ans=0; 
    if(ll<=l&&r<=rr)
        return ans+=a[u].sum;
    int mid=(l+r)/2;
    pushdown(u,l,r);//只要往下走，就把懒惰标记捎下去
    if(ll<=mid)ans+=query(a[u].lc,l,mid,ll,rr);
    if(rr>mid)ans+=query(a[u].rc,mid+1,r,ll,rr);
    return ans;
}
int query_p(int u,int l,int r,int ll) {//单点查询 
    int ans=0; 
    if(ll==l&&r==ll)
        return ans+=a[u].sum;
    int mid=(l+r)/2;
    pushdown(u,l,r);//只要往下走，就把懒惰标记捎下去
    if(ll<=mid)ans=query_p(a[u].lc,l,mid,ll);
    else ans=query_p(a[u].rc,mid+1,r,ll);
    return ans;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)scanf("%d",&A[i]);
    t=1;
    build(1,1,n);
    for(int i=1; i<=m; i++) {
        scanf("%d%d",&q,&x);
        if(q==1) {
            scanf("%d%d",&y,&w);
            update(1,1,n,x,y,w);
        } else {    
            int ans=query_p(1,1,n,x);
            printf("%d\n",ans);
        }
    }
    return 0;
}