线段树初步

    xiaoxiao2021-12-12  22

    最基本的线段树:


    支持区间加,区间查询,带懒标记。

    例题:codevs1082 线段树练习3 题意不再赘述。

    代码:

    #include<iostream> #include<cstdio> using namespace std; const int maxn=2e5+10; inline int getint() { int x=0,f=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,q,data[maxn]; struct segment_tree{int l,r,tag;long long sum;}tree[maxn*4]; void build(int k,int l,int r) { tree[k].l=l,tree[k].r=r; if(l==r){tree[k].sum=data[l];return ;} int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; } void pushdown(int k) { int x=tree[k].r-tree[k].l+1; tree[k<<1].tag+=tree[k].tag; tree[k<<1|1].tag+=tree[k].tag; tree[k<<1].sum+=(x-(x>>1))*tree[k].tag; tree[k<<1|1].sum+=(x>>1)*tree[k].tag; tree[k].tag=0; } void upd(int k,int a,int b,int x) { int l=tree[k].l,r=tree[k].r; if(a==l && b==r) { tree[k].tag+=x; tree[k].sum+=(b-a+1)*x; return ; } if(tree[k].tag) pushdown(k); int mid=(l+r)>>1; if(b<=mid)upd(k<<1,a,b,x); else if(a>mid)upd(k<<1|1,a,b,x); else upd(k<<1,a,mid,x),upd(k<<1|1,mid+1,b,x); tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; } long long ask(int k,int a,int b) { int l=tree[k].l,r=tree[k].r; if(a==l && b==r) return tree[k].sum; if(tree[k].tag) pushdown(k); int mid=(l+r)>>1; if(b<=mid) return ask(k<<1,a,b); else if(a>mid) return ask(k<<1|1,a,b); else return (ask(k<<1,a,mid)+ask(k<<1|1,mid+1,b)); } int main() { n=getint(); for(int i=1;i<=n;i++) data[i]=getint(); build(1,1,n); q=getint(); while(q--) { int t,a,b,x; t=getint(); if(t==1) { a=getint();b=getint();x=getint(); upd(1,a,b,x); } else { a=getint();b=getint(); printf("%lld\n",ask(1,a,b)); } } return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-899984.html

    最新回复(0)