10999번: 구간 합 구하기 2 - 세그먼트 트리(lazy)

lazy propagation 기본 문제

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int MAXN = 1000001;
int N, M, K;
ll segTree[MAXN*4], lazy[MAXN*4];

void setLazy(int idx, int s, int e)
{
    ll val = lazy[idx];
    lazy[idx] = 0;
    
    segTree[idx] += (e-s+1)*val; //lazy 배열의 값을 segTree 배열에 반영
    if(s != e) //값을 자식들에게 밀어주기
    {
        lazy[idx*2] += val;
        lazy[idx*2+1] += val;
    }
}

void update(int s, int e, int l, int r, int idx, ll val)
{
    if(lazy[idx]) setLazy(idx, s, e); //lazy 배열에 뭐가 있다면 처리하기
    
    if(e < l || s > r) return;
    if(l <= s && e <= r)
    {
        segTree[idx] += (e-s+1)*val; //값을 segTree에 반영
        if(s != e) //값을 자식들에게 밀어주기
        {
            lazy[idx*2] += val;
            lazy[idx*2+1] += val;
        }
        return;
    }
    
    update(s, (s+e)/2, l, r, idx*2, val);
    update((s+e)/2+1, e, l, r, idx*2+1, val);
    segTree[idx] = segTree[idx*2] + segTree[idx*2+1];
}

ll sum(int s, int e, int l, int r, int idx)
{
    if(lazy[idx]) setLazy(idx, s, e); //lazy 배열에 뭐가 있다면 처리하기
    
    if(e < l || s > r) return 0;
    if(l <= s && e <= r) return segTree[idx];
    
    return sum(s, (s+e)/2, l, r, idx*2) + sum((s+e)/2+1, e, l, r, idx*2+1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

    cin >> N >> M >> K;
    for(int i=1; i<=N; i++)
    {
        ll val; cin >> val;
        update(1, N, i, i, 1, val);
    }
    
    for(int i=1; i<=M+K; i++)
    {
        int a; cin >> a;
        if(a == 1)
        {
            ll b, c, d; cin >> b >> c >> d;
            update(1, N, b, c, 1, d);
        }
        else
        {
            ll b, c; cin >> b >> c;
            cout << sum(1, N, b, c, 1) << "\n";
        }
    }
}