[Link Cut Tree] 5. 구간 갱신(Lazy Propagation)

세그먼트 트리나 Splay Tree에서 구간 갱신을 위해서 Lazy Propagation을 쓰듯, 트리에서 경로상의 값들을 모두 갱신해주기 위해서 Link Cut Tree에서도 Lazy Propagation을 사용해야 합니다.

x에서 y까지의 경로에 있는 모든 노드의 값에 val을 더하는 연산을 구현해보도록 합시다.

void lazy(node * x) {
    if (!x->lazy) return;
    if (x->l) {
        x->l->val += x->lazy;
        x->l->sum += x->lazy * x->l->cnt;
        x->l->lazy += x->lazy;
    }
    if (x->r) {
        x->r->val += x->lazy;
        x->r->sum += x->lazy * x->r->cnt;
        x->r->lazy += x->lazy;
    }
    x->lazy = 0;
}

먼저 Lazy를 전파하는 함수를 만들어 줍니다.

void splay(node * x) {
    while (!isRoot(x)) {
        node * p = x->p;
        if (!isRoot(p)) lazy(p->p);
        lazy(p);
        lazy(x);
        if (!isRoot(p)) {
            if ((x == p->l) == (p == p->p->l)) rotate(p);
            else rotate(x);
        }
        rotate(x);
    }
    lazy(x);
}

splay 함수에 Lazy를 전파하는 부분을 삽입합니다.

Splay Tree에서는 임의의 노드에 접근하지 않고 루트에서부터 접근하지만, Link Cut Tree는 임의의 노드에 직접 접근하는 경우가 많아서 splay나 rotate에서 lazy를 갱신합니다.

위 코드에서는 splay 함수에서 Lazy 전파를 했는데, 반복문을 돌면서 바뀌는 노드들만 Lazy를 잘 전파해주면 splay가 끝난 후에 루트는 Lazy가 모두 갱신된 상태가 됩니다.

단, 주의할 점은 노드에 직접 접근하지 않고 다른 노드에서 간접적으로 접근하는 경우에는 Lazy를 따로 전파해주어야 한다는 것입니다.

지금까지 구현한 Link Cut Tree에는 루트 없는 트리에서 임의의 두 노드를 붙이는 것이 불가능하다는 한계점을 가지고 있습니다.

Lazy propagation을 사용하면 Splay Tree를 뒤집는 것도 가능한데, 이것을 Link Cut Tree에 적용하면 트리의 루트를 동적으로 바꿔가면서 트리의 임의의 두 노드를 붙일 수 있습니다.

void makeRoot(node * x) {
    access(x);
    x->reverse = !x->reverse;
}

makeRoot 함수는 원하는 노드를 포함된 트리의 루트로 만드는 연산입니다.

코드를 올리지는 않았지만, node 구조체에 bool reverse를 추가하고 lazy 함수에 reverse를 전파하는 부분를 만들어줘야 합니다.

x와 루트를 연결하는 경로를 뒤집으면 x가 가장 왼쪽의 노드가 되어서 x가 트리의 루트로 바뀌게 됩니다.

이제 link 연산을 통해 원하는 노드를 연결해주면 됩니다.