구간의 합 2 (JUNGOL 8082)

https://jungol.co.kr/problem/8082?cursor=MTIsMSww

---

아이디어

느리게 갱신되는 세그먼트 트리의 기본 문제입니다. lazy[node]를 node에 저장된 갱신값이라고 정의하며, pp(s,e,node)를 node에 저장된 갱신값을 tree값으로 옮기고 자식에게 갱신값을 물려주는 함수로 정의합니다.

---

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll tree[4040404]={0},lazy[4040404]={0};
void pp(ll s,ll e,ll node)
{
    tree[node]+=lazy[node]*(e-s+1);
    if (s!=e)
    {
        lazy[node*2]+=lazy[node];
        lazy[node*2+1]+=lazy[node];
    }
    lazy[node]=0;
}
void update(ll s,ll e,ll node,ll l,ll r,ll num)
{
    pp(s,e,node);
    if (e<l || r<s) return;
    if (l<=s && e<=r)
    {
        lazy[node]=num;
        pp(s,e,node);
        return;
    }

    ll mid=(s+e)/2;
    update(s,mid,node*2,l,r,num);
    update(mid+1,e,node*2+1,l,r,num);
    tree[node]=tree[node*2]+tree[node*2+1];
}
ll Sum(ll s,ll e,ll node,ll l,ll r)
{
    pp(s,e,node);
    if (e<l || r<s) return 0;
    if (l<=s && e<=r) return tree[node];
    ll mid=(s+e)/2;
    return Sum(s,mid,node*2,l,r)+Sum(mid+1,e,node*2+1,l,r);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,Q,i,a,b,c,x;

    cin>>N;
    for (i=1;i<=N;i++)
    {
        cin>>x;
        update(1,N,1,i,i,x);
    }

    cin>>Q;
    for (i=0;i<Q;i++)
    {
        cin>>a;

        if (a==1)
        {
            cin>>b>>c>>x;
            update(1,N,1,b,c,x);
        }
        else
        {
            cin>>b>>c;
            cout<<Sum(1,N,1,b,c)<<"\n";
        }
    }
}