개념

링크

참고 블로그

세그먼트 트리 나중에 업데이트 해야지!

응용문제

10999번: 구간 합 구하기 2

설명

Segment Tree에서 특정 구간을 같은 값으로 update할 때 모든 원소에 대하여 update를 실행하면 시간이 오래 걸린다. 여기서 Lazy Propagation라는 기법을 쓰면 시간을 단축 시킬 수 있다.

예를 들어 2~4번째 원소에 전부 1을 더해준다고 해보자. Segment Tree에서는 구간 (2~4)를 대표하는 노드로 (2-2), (3-4)가 있다. 이 두 노드를 대표노드라고 하자. (2-2)는 마지막 노드지만 (3-4)는 (3-3), (4-4)로 나뉘어 지는 노드이다. 우선 대표노드에만 변경값을 적용 시킨다. 그리고 나중에 Sum함수를 실행할 때 업데이트 해주면 된다. 변경되는 값은 Lazy라는 배열에 저장해 둔다.

update_lazy 함수

현재 노드에 저장되어 있는 Lazy를 적용시켜주는 함수이다.

현재 노드의 Lazy값을 Tree에 적용시켜주고 Child의 Lazy에 Lazy값을 전달한다. 적용을 마친 현재노드의 Lazy는 0으로 변경해준다.

Sum함수를 호출할떄마다 실행해준다.

update_range 함수

Lazy Propagation을 시작하는 함수이다. Start, End, Left, Right 범위를 비교해가면서 구간의 대표노드를 찾는다. 대표노드가 도착했으면 변경값을 적용시킨다. 대표노드가 마지막 노드가 아니라면 child의 Lazy에 값을 변경값을 넣어준다. 추후에 child에 update_lazy함수가 실행되면 처리한다. Sum 함수가 실행되기 전까지는 update_range함수로 계속 변경이 가능하다. update_range를 여러번 사용하는 경우 대표노드로 접근하면서 앞서 lazy가 저장된 노드를 지날 때는 update_lazy를 실행해서 lazy값을 적용 시켜줘야한다.

코드

글로 설명이 어려우니 코드로 보자.

void update_range(int left, int right, T diff) {
        update_range(0, end, 1, left, right, diff);
    }

void update_range(int start, int end, int node, int left, int right, T diff) {
    update_lazy(start, end, node);
    if (end < left || right < start) return;
    if (left <= start && end <= right) {
        tree[node] += (end - start + 1) * diff;
        if (start != end) {
            lazy[2 * node] += diff;
            lazy[2 * node + 1] += diff;
        }
        return;
    }
    int mid = (start + end) / 2;
    update_range(start, mid, 2 * node, left, right, diff);
    update_range(mid + 1, end, 2 * node + 1, left, right, diff);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

void update_lazy(int start, int end, int node) {
    if (lazy[node] == 0) return;
    tree[node] += (end - start + 1) * lazy[node];
    if (start != end) {
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
    }
    lazy[node] = 0;
}