[백준 10999번] [Lazy propagation] 구간 합 구하기 2

Approach

단순히 세그먼트 트리로 구간에 대한 정보를 모두 처리하게 되면, 업데이트마다 MlgN만큼이 필요하게 된다. (단, M은 b ~ c 사이의 개수)

최악의 경우 NlgN이 필요하다.

 

따라서 단순히 세그먼트 트리로 이 문제를 해결할 경우 O(NKlgN) = 1000000 * 10000 * log10000이므로 무조건 시간 초과를 받게 된다.

 

위와 같은 상황에서 사용할 수 있는 자료구조가 Lazy propagation이다.

해당하는 자료는 다음을 참고하도록 하자.

https://m.blog.naver.com/kdr06006/221818523719

세그먼트 트리 with Lazy Propagation

Lazy propagation을 활용하면 업데이트에서 필요한 시간이 lgN이면 충분하다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};

ll seg[4000000];
ll lazy[4000000];

void propagate(int node, int left, int right){
    if(lazy[node]){
        if(left != right){
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        seg[node] += lazy[node] * (right - left + 1);
        lazy[node] = 0;
    }
}

void update(int node, int start, int end, int left, int right, ll value){
    propagate(node, start, end); // 일단 propagate
    if(end < left || right < start) return;
    if(left <= start && end <= right){
        lazy[node] += value;
        propagate(node, start, end);
        return;
    }
    // 일부만 포함된 경우에는 다시 update를 진행해주어야 함(자식 중 일부가 갱신된 것이므로)
    int mid = (start + end) >> 1;
    update(node * 2, start, mid, left, right, value);
    update(node * 2 + 1, mid + 1, end, left, right, value);
    seg[node] = seg[node * 2] + seg[node * 2 + 1];
}

ll query(int node, int start, int end, int left, int right){
    propagate(node, start, end);
    if(right < start || end < left) return 0;
    if(left <= start && end <= right) return seg[node];
    int mid = (start + end) >> 1;
    return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right);
}

int main() {
    fastio;
    memset(seg, 0, sizeof(seg));
    memset(lazy, 0, sizeof(lazy));

    ll n, m, k;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        ll t;
        cin >> t;
        update(1, 1, 1000000, i, i, t);
    }
    ll a, b, c, d;
    for(int i = 0; i < m + k; i++){
        cin >> a;
        if(a == 1){
            cin >> b >> c >> d;
            update(1, 1, 1000000, b, c, d);
        }
        else{
            cin >> b >> c;
            cout << query(1, 1, 1000000, b, c) << "\n";
        }
    }
    return 0;
}