首页 > 其他 > 详细

P3372 【模板】线段树 1

时间:2019-08-17 16:59:59      阅读:82      评论:0      收藏:0      [点我收藏+]
#include<cstdio>
using namespace std;
struct ben
{
    long long l,r,val,mark;
}tr[400005];
long long a[100005];
void bt(long long x,long long l,long long r)
{
    tr[x].l=l;
    tr[x].r=r;
    if(l==r)
    {
        tr[x].val=a[l];
        return ;
    }
    long long lch=x*2;
    long long rch=x*2+1;
    long long mid=(l+r)/2;
    bt(lch,l,mid);
    bt(rch,mid+1,r);
    tr[x].val=tr[lch].val+tr[rch].val;
}
void Down(long long x)//标记下传
{
    if(tr[x].mark&&tr[x].l<tr[x].r)
    {
        long long lch=x*2;
        long long rch=x*2+1;
        tr[lch].val+=tr[x].mark*(tr[lch].r-tr[lch].l+1);
        tr[lch].mark+=tr[x].mark;
        tr[rch].val+=tr[x].mark*(tr[rch].r-tr[rch].l+1);
        tr[rch].mark+=tr[x].mark;
    }
    tr[x].mark=0;
}
void mority(long long x,long long l,long long r,long long k)
{
    Down(x);
    if(l<=tr[x].l&&tr[x].r<=r)
    {
        tr[x].val+=k*(tr[x].r-tr[x].l+1);
        tr[x].mark+=k;
        return ;
    }
    long long lch=x*2;
    long long rch=x*2+1;
    long long mid=(tr[x].l+tr[x].r)/2;
    if(l<=mid)
    mority(lch,l,r,k);
    if(r>mid)
    mority(rch,l,r,k);
    tr[x].val=tr[lch].val+tr[rch].val;
}
long long query(long long x,long long l,long long r)
{
    release(x);
    if(l<=tr[x].l&&tr[x].r<=r)
    {
        return tr[x].val;
    }
    long long lch=x*2;
    long long rch=x*2+1;
    long long mid=(tr[x].l+tr[x].r)/2;
    long long ans=0;
    if(l<=mid)
    ans+=query(lch,l,r);
    if(r>mid)
    ans+=query(rch,l,r);
    return ans;
}
int main()
{
    long long n,m;
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    bt(1,1,n);
    long long pd,x,y,k;
    for(long long i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&pd,&x,&y);
        if(pd==1)
        {
            scanf("%lld",&k);
            mority(1,x,y,k);
        }
        else
        {
            printf("%lld\n",query(1,x,y));
        }
    }
    return 0;
} 

P3372 【模板】线段树 1

原文:https://www.cnblogs.com/ShineEternal/p/11368913.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!