[구간쿼리] Lazy Propagation

처리해야 할 쿼리

이전 글에서는 다음 두 가지 쿼리가 주어졌습니다.

구간 [l, r]이 주어졌을 때 해당 구간의 합 구하기
i번째 수를 v로 바꾸기

이번 글에서는 2번 쿼리가 바뀝니다.

구간 [i, j]의 모든 값을 v로 바꾸기 쿼리는 최대 M개 입니다.

이전 글에서 다뤘던 세그먼트 트리는 2번 쿼리를 O(N log N)에 수행합니다.
하지만, update함수를 변경하면 O(log N)에 가능합니다.

작동 방식

이 아이디어는 “업데이트를 미룬다” 라는 것을 기본으로 시작합니다.

[3, 8] 구간에 5를 더한다고 가정해봅시다.

회색 노드는 담당하고 있는 구간이 [3, 8]에 일부만 포함되는 경우, 초록색 노드는 모두 포함되는 경우입니다.
회색 노드는 이전 글에서 썼던 update 방식을 그대로 쓰면 되지만, 초록색 노드는 다른 방법을 써야합니다.

일단 초록색 노드들은 값을 업데이트 해주고, 각각의 자식노드들은 나중에 필요할 때 하기로 하고, 그 값을 lazy배열에 저장합시다.
업데이트를 할 때마다 lazy배열의 값이 0인지 아닌지 확인을 해주고, 0이 아니라면 업데이트를 해야한다는 것을 의미하므로 노드에 올바른 값을 더해주고, 자식들에게 lazy값을 물려주어야 합니다.

구현

init

먼저, init코드는 똑같습니다.

typedef long long ll;
typedef vector<ll> vll;

ll init(vll &arr, vll &tree, int node, int start, int end){
    if(start == end){
        return tree[node] = arr[start];
    }
    return tree[node] = init(arr, tree, node*2, start, (start+end)/2) + init(arr, tree, node*2+1, (start+end)/2+1, end);
}

update

update함수는 update_lazy함수와 update_range함수로 분리가 됩니다.
update_lazy함수는 lazy값을 노드에 적절하게 업데이트하고 자식들에게 물려주는 역할을 수행하고,
update_range함수는 원하는 범위의 값을 업데이트 하는 역할을 합니다.

void update_lazy(vll &tree, vll &lazy, int node, int start, int end){
    if(lazy[node] != 0){ //업데이트를 해야 할 경우
        tree[node] += (end-start+1) * lazy[node]; //관할 구역의 개수만큼 더함
        if(start != end){ //리프 노드가 아니면
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0; //업데이트 완료
    }
}

void update_range(vll &tree, vll &lazy, int node, int start, int end, int left, int right, ll diff){
    update_lazy(tree, lazy, node, start, end); //lazy값이 남아있으면 갱신

    if(left>end || right<start){ //범위 초과
        return;
    }
    if(left<=start && end<=right){ //범위 포함
        tree[node] += (end-start+1) * diff;
        if(start!=end){
            lazy[node*2] += diff;
            lazy[node*2+1] += diff;
        }
        return;
    }
    update_range(tree, lazy, node*2, start, (start+end)/2, left, right, diff);
    update_range(tree, lazy, node*2+1, (start+end)/2+1, end, left, right, diff);
    tree[node] = tree[node*2] + tree[node*2+1];
}

sum

sum함수는 update_lazy를 한 번 호출하는 것을 제외하고는 이전과 같습니다.

ll sum(vll &tree, vll &lazy, int node, int start, int end, int left, int right){
    update_lazy(tree, lazy, node, start, end);
    if(left>end || right<start) return 0;
    if(left<=start && end<=right) return tree[node];
    return sum(tree, lazy, node*2, start, (start+end)/2, left, right) + sum(tree, lazy, node*2+1, (start+end)/2+1, end, left, right);
}

처리해야 할 쿼리

작동 방식

구현

init

update

sum

추천 문제