Lazy propagation

사전 지식

---

segment tree에서 하나의 값을 업데이트하는 연산의 시간복잡도는 O(logN) (N : 배열의 길이)인데, 나머지 수들도 변경해줘야하므로

총 걸리는 시간복잡도은 O(NlogN)이다.

그런데, 이전에서 다룬 것 처럼 한번에 하나의 수를 업데이트 하는것이 아닐 경우의 시간 복잡도는 어떨까?

10개의 수 1, 10, 3, 6, 5, 6, 4, 2, 9, 7에 대해 3번째 수부터 6번째 수까지 5씩 더하는 업데이트해야 하는 경우을 생각해보자.

이전 포스팅에서 사용한 업데이트 방식을 사용하면 업데이트 함수를 3,4,5,6번째 숫자에 대해 각각 호출해야한다.

즉, 길이 N인 배열에 질의가 K번 들어올 때 (for문과 같은 반복문을 사용할 경우) 전체 업데이트에 O(NKlogN)의 시간복잡도 필요하다.

이를 Lazy propagation을 사용해 구간 업데이트 연산을 효율적으로 할 수 있다. 즉 update 시간을 줄일 수 있는 방법이다.

하나씩 업데이트해서 구간을 업데이트하는 것이 아니라 한번에 그 구간을 대표하는 노드를 수정해서 O(logN)만에 구간을 업데이트 할 수 있다.

---

Lazy propagation 게으른 전파

• 개념 : segment tree에서 update할시, 모든 노드들을 바로 업데이트하는 것이 아닌 쿼리에 필요한 노드들만 업데이트 하는 방법 → 꼭 필요할 때가 오기 전까지 업데이트를 미룬다.
• 구현 방법 : 기존의 segment tree 배열말고, 노드에 업데이트할 값을 저장할 새로운 일차원 배열 필요

  (이 배열이 의미하는 바는, 이 노드의 영역 전체에 얼마만큼의 값을 더할 계획이 있다 라는 것이다.)

• 구현 코드

#include <stdio.h>
using namespace std;
 
typedef long long ll;
int n, m, k;
ll tree[4000000]; //세그먼트 트리 배열
ll lazy[4000000]; //업데이트할 값을 저장하는 배열
 
void propagation(int node,int nodeL,int nodeR) {
    tree[node] += lazy[node] * (nodeR - nodeL + 1); //영역 구간의 크기만큼 업데이트해준다.

    if (nodeL != nodeR) { //리프노드가 아니라면
        lazy[node * 2] += lazy[node]; //왼쪽 자식에게 전파
        lazy[node * 2 + 1] += lazy[node]; //오른쪽 자식에게 전파
    }

    lazy[node] = 0; //전파했으므로 0으로 초기화
}
 
// [L,R] 업데이트 할 구간, val 업데이트할 값 , node 현재 노드, [nodeL,nodeR] 현재 구간 
void update(int L,int R,ll val,int node,int nodeL,int nodeR) {
    if (lazy[node] != 0) propagation(node, nodeL, nodeR); //만일 update해야한다면, propagation 호출
    if (nodeL > R || nodeR < L) return;
    if (L <= nodeL && nodeR <= R) { //현재 구간이 업데이트 
        lazy[node] += val;
        propagation(node, nodeL, nodeR);
        return;
    }
    int mid = (nodeL + nodeR) / 2;
    update(L,R, val, node*2, nodeL, mid);
    update(L,R, val, node*2+1, mid + 1, nodeR);
    //마지막에 자식들의 값을 사용해 다시 자신의 값 갱신
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
 
// [L,R] 구할 쿼리 구간, node 현재 노드, [nodeL,nodeR] 현재 구간 
ll query(int L, int R, int node, int nodeL, int nodeR) {
    if (lazy[node] != 0) propagation(node, nodeL, nodeR); //만일 update해야한다면, propagation 호출
    if (nodeR < L || R < nodeL) return 0;
    if (L <= nodeL && nodeR <= R) return tree[node];
    int mid = (nodeL + nodeR) / 2;
    return query(L, R, node * 2, nodeL, mid) + query(L, R, node * 2 + 1, mid + 1, nodeR);
}
 
int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++) {
        int temp;
        scanf("%d", &temp);
        update(i,i, temp, 1, 1, n);
    }
    for (int i = 0; i < m + k; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b,&c);
        if (a == 1) {
            ll d;
            scanf("%lld", &d);
            update(b, c, d, 1, 1, n);
        }
        else {
            printf("%lld\n", query(b, c, 1, 1, n));
        }
    }
    return 0;
}