线段树入门——区间求和，区间更新

佚名 6年前 (2019-04-23) 随笔 2088人围观抢沙发百度已收录

线段树入门区间求和，区间更新。

题目链接：https://cn.vjudge.net/problem/POJ-3468

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=100000;
const int maxsize=4*maxn;

struct Node
{
    ll sum;
    ll tag;
};

Node data[maxsize];

void add(int v,int a,int b,int k,int l,int r)
{
    if(b<=l||a>=r)
        return;
    if(a<=l&&b>=r)
        data[k].tag+=v;
    else
    {
        data[k].sum+=(min(r,b)-max(l,a))*v;
        add(v,a,b,2*k+1,l,(l+r)/2);
        add(v,a,b,2*k+2,(l+r)/2,r);
    }
}

ll query(int a,int b,int k,int l,int r)
{
    if(b<=l||a>=r)
        return 0;
    if(a<=l&&b>=r)
        return data[k].tag*(r-l)+data[k].sum;

    ll sum=0;
    sum+=data[k].tag*(min(r,b)-max(l,a));
    sum+=query(a,b,2*k+1,l,(l+r)/2);
    sum+=query(a,b,2*k+2,(l+r)/2,r);

    return sum;
}

int main()
{
    int n,q,t,a,b;
    char c;
    scanf("%d%d",&n,&q);

    for(int i=0;i<n;++i)
    {
        scanf("%d",&t);
        add(t,i,i+1,0,0,n);
    }

    while(q--)
    {
        scanf("%*c%c%d%d",&c,&a,&b);
        if(c=='Q')
            printf("%lld\n",query(a-1,b,0,0,n));
        else
        {
            scanf("%d",&t);
            add(t,a-1,b,0,0,n);
        }
    }

    return 0;
}