线段树模板

小咪咪 2023-08-17 17:08 69阅读 0赞

P3372 【模板】线段树 1

#include<cstdio>
    #include<iostream>
    using namespace std;
    #define MAXN 1000099
    #define LLD long long int
    #define ls id*2
    #define rs id*2+1
    int n,m,opt,x,y,k;
    int A[MAXN],B[MAXN];
    LLD num[MAXN],lazy[MAXN];
    void Build(int id,int L,int R)
    {
        A[id]=L;
        B[id]=R;
        if(L==R)
        {
            cin>>num[id];
            return ;
        }
        int mid=(L+R)/2;
        Build(ls,L,mid);
        Build(rs,mid+1,R);
        num[id]=num[ls]+num[rs];
    }
    void down(int id)
    {
        num[id]+=lazy[id]*(B[id]-A[id]+1);
        if(A[id]<B[id])
        {
            lazy[ls]+=lazy[id];
            lazy[rs]+=lazy[id];
        }
        lazy[id]=0;
    }
    void add(int id,int L,int R,LLD val)
    {
        down(id);
        if(A[id]==L && B[id]==R)
        {
            lazy[id]+=val;
            return ;
        }
        int mid=(A[id]+B[id])/2;
        if(R<=mid) add(ls,L,R,val);
        else if(mid<L) add(rs,L,R,val);
        else
        {
            add(ls,L,mid,val);
            add(rs,mid+1,R,val);
        }
        num[id]=num[ls]+lazy[ls]*(B[ls]-A[ls]+1)+num[rs]+lazy[rs]*(B[rs]-A[rs]+1);
    }
    LLD sum(int id,int L,int R)
    {
        down(id);
        if(A[id]==L && B[id]==R) return num[id];
        int mid=(A[id]+B[id])/2;
        if(R<=mid) return sum(ls,L,R);
        else if(mid<L) return sum(rs,L,R);
        else
        {
            return sum(ls,L,mid)+sum(rs,mid+1,R);
        }
    }
    int main()
    {
        freopen("test.in","r",stdin);
        cin>>n>>m;
        Build(1,1,n);
        for(int i=1; i<=m; i++)
        {
            cin>>opt;
            if(opt==1)
            {
                cin>>x>>y>>k;
                add(1,x,y,k);
            }
            else
            {
                cin>>x>>y;
                cout<<sum(1,x,y)<<endl;
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/D-O-Time/p/11248722.html