지연 연산 - 알고리즘카

다음과 같이 문제를 변형해 봅시다. 크기가 $n$인 배열이 주어지고, 다음 두 가지 유형의 쿼리에 답해야 합니다:

구간 $[l, r)$의 모든 값을 $x$로 바꿉니다($l$부터 $r$까지의 모든 $k$에 대해 a[k] = x를 수행합니다).
$l$부터 $r$까지의 구간에 있는 원소 $a_i$의 합을 출력합니다.

즉, 이제 갱신 쿼리는 원소 하나가 아니라 어떤 구간 $[l, r)$의 모든 원소에 값 $x$를 대입하는 것이며, 그러면서도 여전히 두 쿼리를 모두 $O(\log n)$에 처리하고자 합니다.

#기본 아이디어

합이 바뀌는 모든 원소까지 내려가고 싶지는 않습니다. 그런 원소는 매우 많을 수 있기 때문입니다.

대신 우리는 꾀를 부려, 대입 쿼리가 들어오면 가능한 한 일부 정점에 그 정점과 모든 자식이 어떤 수 $d_v = x$와 같아야 한다는 «표시»를 해 두고, 더 아래로 내려가서 이 대입을 직접 수행하지는 않을 것입니다.

예를 들어 “배열 전체에 수 $x$를 대입하라"는 쿼리가 들어오면, 실제 대입은 어디에서도 전혀 하지 않습니다. 트리의 루트에 그 안의 모든 원소가 $x$와 같다는 표시만 남겨 둡니다.

나중에 이러한 노드와 그 자식들의 올바른 값이 필요해지면, 루트에서 내려가는 경로를 따라 현재 노드의 정보를 자식들에게 «밀어 넣기(push)»를 수행합니다. 즉, 표시가 있으면 현재 구간의 합을 다시 계산하고 그 표시를 자식들에게 전달합니다(자식들에 대해 재귀적으로 실행하지는 않습니다). 이후에 자식들의 필드가 필요해지면 같은 작업을 수행합니다. 즉, 자식들에서 합을 다시 계산하고 표시를 그 자식들에게 전달하며, 이런 식으로 계속합니다. 이러한 연산은 노드의 데이터가 필요해지는 바로 그 시점까지 데이터가 올바르다는 것을 보장합니다.

작업이 절약되는 이유는, 이미 어떤 표시가 있는 자식에게 표시를 전달하면 그 표시가 단순히 덮어쓰여서 이전의 대입들을 더 이상 수행할 필요가 없기 때문입니다. 작업을 미루는 것의 이점은 이러한 지연 연산 중 일부를 나중에 수행할 필요가 없어진다는 데 있습니다.

이러한 ‘지연된’ 갱신을 사용해도 점근적 복잡도는 전혀 나빠지지 않습니다. 경로상의 각 정점에서 지연 연산을 하나씩 수행하므로 연산이 $O(1)$만큼 더 늘어날 뿐이며, 따라서 여전히 모든 쿼리에 $O(\log n)$에 답할 수 있습니다.

#구현

표시 필드 assign을 추가하고, 이 정점의 정보를 두 자식 모두에게 밀어 넣는 보조 함수 push를 만듭시다.

struct Segtree {
    int lb, rb;
    int sum = 0, assign = -1; // "-1" означает, что присвоения делать не нужно
    Segtree *l = 0, *r = 0;
    
    Segtree(int lb, int rb) : lb(lb), rb(rb) {
        if (lb + 1 < rb) {
            int t = (lb + rb) / 2;
            l = new segtree(lb, t);
            r = new segtree(t, rb);
        }
    }
    
    void push() {
        if (assign != -1) {
            sum = (rb - lb) * assign;
            if (l) { // если дети есть
                l->assign = assign;
                r->assign = assign;
            }
        }
        assign = -1;
    }
};

push 메서드는 모든 쿼리를 처리하기 시작할 때 맨 먼저 호출하는 것이 좋습니다. 그러면 현재 노드의 모든 값이 올바르다는 것이 보장되고, 자식 노드에는 재귀적으로 내려가 그 노드에서 push를 호출할 때 값이 올바르게 되기에 충분한 정보가 담기게 됩니다.

void add(int lq, int rq, int x) {
    push();
    if (lq <= lb && rb <= rq)
        assign = x;
    else if (l && max(lb, lq) < min(rb, rq)) {
        // если есть дети и отрезок запроса хоть как-то пересекается с нашим
        l->add(lq, rq, x);
        r->add(lq, rq, x);
        // ...дальше они сами разберутся
    }
}

int sum(int lq, int rq) {
    push();
    if (lb >= lq && rb <= rq)
        return s;
    if (max(lb, lq) >= min(rb, rq))
        return 0;
    return l->sum(lq, rq) + r->sum(lq, rq);
}

영어로는 이 기법을 lazy propagation이라고 부릅니다. “모든 것을 마지막 순간에 하자"라는 일반적인 아이디어는 세그먼트 트리뿐만 아니라 다른 자료구조 ~~그리고 실생활~~에서도 적용할 수 있습니다.