자료구조 - 세그먼트 트리(Segment Tree)2 - 느린 전파

 

이번 내용은 지난 세그먼트 트리(Segment Tree) 자료구조 포스팅에 이어서 느린 전파(Lazy Propagation) 기능에 대해 설명하는 포스팅입니다. 지난 포스팅은 아래 링크를 참고

hongjw1938.tistory.com/20 

자료구조 - 세그먼트 트리(Segment Tree)

 

1. 세그먼트 트리

 

아래의 그림을 보면서 세그먼트 트리의 기존 구조를 복습해 보자.

세그먼트 트리 데이터 7개 구간 연산 예시

 

위 그림에서 합 연산의 결과를 얻고자 한다면 어느 정도의 연산이 필요할까? 예를 들어 arr[4]~arr[6] 까지의 합의 결과를 원한다고 가정하자.

이전 포스팅에서와 같이 구간 합의 결과를 반환하는 경우의 수는 총 3가지이다.

1) 원하는 구간이 현재 탐색 중인 대표노드가 갖는 구간과 정확히 일치할 때
예) arr[5] ~ arr[6]의 합은 6번 노드(대표노드)의 결과로 종료

2) 원하는 구간이 현재 탐색 중인 대표노드가 갖는 구간과 겹치는 부분이 없을 때
예) arr[3] ~ arr[4]의 합을 구한다면 1번에서 3번(Right Child) 노드로 탐색 시 구간이 전혀 겹치지 않아 추가 탐색 불 필요

3) 원하는 구간이 현재 탐색 중인 대표노드가 갖는 구간의 일부 일 때
예) arr[3] ~ arr[4]의 합을 원하는데 현재 2번 노드 탐색 중이라면, 추가로 5번 노드까지 탐색 수행 필요

그렇다면 arr[4] ~ arr[6]의 합을 원하는 경우 탐색 경로는 아래와 같다.
① 1번 → 2번 → 5번 → 11번 탐색하여 arr[4] 반환
② 1번 → 3번 → 6번 탐색하여 arr[5]~arr[6] 반환

이를 그림으로 표현해본다면 아래와 같다. 붉은 자수정과 같은 색상의 경로로 탐색한다고 볼 수 있다.

 

 

만약, arr[5]의 숫자가 다른 값으로 변경되었다면 어떨까? 이 때 영향을 받는 구간의 대표노드들은 아래와 같다.
영향 받는 노드 : 1번, 3번, 6번, 12번

이와 같이, 합 연산의 결과를 반환하거나 변경된 값을 반영 시에 각각 O(logN) 정도의 시간복잡도를 가지게 되는 것을 알 수 있는데, 합 / 변경을 1회로 총 M회 수행한다면 전체 시간복잡도는 아래와 같을 것이다.
총 시간복잡도 : O(MlogN)

 

 

2. 구간 업데이트

 

위와 같은 상황일 때, 한 가지 상황을 추가해보자. 이전에는 하나의 값만 변경하였는데, 이제는 구간에 있는 모든 값을 변경해야 한다는 가정을 해보자.

예를 들어 arr[1] ~ arr[6] 까지의 모든 구간 내 값들을 기존 값 대비 5씩 더해야 하는 경우가 필요하다면 어떨까?

그렇다면 이전 포스팅의 업데이트 방식을 그대로 활용한다고 볼 때, 업데이트 함수를 arr[1] ~ arr[6]까지 모두 호출해야 할 것이다. 이 때의 시간복잡도는 최악의 경우 전체 구간을 업데이트 한다면 O(NlogN)이 될 것이다.

만약 이 전체 업데이트를 M회 진행한다면 최악의 경우 O(N * M * logN)이 된다.

이는 너무나 오랜 시간을 소요할 수 있다. 이 보다 더 빠르게 수행할 수 있는 방법이 없을까? 그것이 느린 전파(Lazy Propagation) 기법이다.

 

3. 느린 전파(Lazy Propagation)

 

말 그대로 게으르게 업데이트를 전파하는 방식이다. 구간에 있는 모든 값을 업데이트한다면 해당 구간을 대표하는 대표노드에 변경되는 만큼의 정보를 저장해두고 당장 전파하지 않고 추후에 전파하는 방식을 의미한다.

이 방식을 통해 전체 업데이트를 O(logN) 만에 가능하도록 할 수 있는 개념이다. 어떻게 가능한지 살펴보자.

자, 위에서 든 예시와 같이 arr[1] ~ arr[6]의 구간 내 데이터를 모두 5씩 더해준다고 생각해보자. 그렇다면 이 구간들을 대표하는 노드에 변경되는 정보를 저장하두어야 한다.

이와 같이 별도로 변경되는 정보를 저장하는 배열을 따로 생성해야 하는데, 이것을 지금부터 lazy 라고 부르도록 한다.

아래의 그림을 보자. 변경 구간의 대표노드는 빨간색으로 칠하였고 해당 대표노드의 lazy는 보라색으로 칠해두었다.

 

구간 업데이트 Lazy 정보 저장

 

자, 이와 같이 해당 구간을 대표하는 2번 노드(arr[1]~arr[4] 대표, 배열 인덱스 2) / 6번 노드(arr[5]~arr[6] 대표, 배열 인덱스 6)에 업데이트 정보를 저장해두었다고 생각해보자.

그럼, 이 정보를 저장해 두었으니, 업데이트가 완료된 것일까? 당연히 아니다. 만약 이 업데이트를 수행한 뒤에 갑자기 arr[2]~arr[5] 까지의 합의 정보를 원한다고 생각해보자.

그렇다면 세그먼트 트리의 합을 구하는 로직에 따라서 9번 (arr[2] 의 대표) / 5번 (arr[3]~arr[4] 의 대표) / 12번 (arr[5] 의 대표)  노드들을 방문하여 그 값을 반환하고 전부 더하려고 할 것이다. 그런데! 현재 lazy의 정보는 2번 / 6번 노드에만 저장되어 있어 전파가 완료되지 않았기 때문에 답은 잘못된 결과를 초래하고 말 것이다.

그래서, 이 정보를 그 아래 구간에 모두 전파를 시켜야만 한다. 하지만, 업데이트를 할 때마다 모든 노드에 다 전파단순를 시키고자 한다면 단순 업데이트와 차이가 없을 것이다. 그래서 느리게 전파시키는 기법이 여기서 사용된다.

 

어떻게 게으르게(느리게) 전파시킬 수 있을까?

세그먼트 트리의 구조를 잘 생각해보자. 각각의 자식 노드에 도달하기 위해서는 반드시 부모 노드를 거쳐야 하는 구조이다. 그래서 부모 노드에 만약 lazy 정보가 있다면 전파를 시키는 방법을 활용하면 된다.

간단하게 예시를 들어보자. 만약 위와 같이 arr[1]~arr[6]에 모두 5씩 더하는 업데이트에 이어 곧바로 arr[3]~arr[4]를 또 다시 3씩 더하는 업데이트가 주어졌고 이에 전체 구간 합을 구하라는 지시가 내려졌다고 가정해보자.

① arr[1] ~ arr[6] 의 모든 구간에 +5
② arr[3] ~ arr[4] 의 모든 구간에 +3
③ arr[1] ~ arr[7] 까지 모든 구간의 합 구하기

 

자, 우선 ① 과정 부터 대략 그림으로 알아보자.

 

루트에서 부터 탐색 시작!

 

구간 대표를 찾아 lazy 업데이트!

 

간단하게 그림으로 보면 최상단 노드에서 시작하여 업데이트 구간의 대표 노드를 찾으면 해당 노드에 lazy를 저장하고 바로 적용 시킨 뒤 자신의 자식 노드들에 전파시킨다.

아까의 상단 그림에서는 대표 노드에만 lazy를 저장했는데 실질적으로 코드상으로는 위와 같이 동작한다. 현재는 2번 노드와 6번 노드가 대표 노드이므로 바로 적용시키고 자신의 자식 노드들에게 lazy를 전파 시킨 상황이다.

이 때, 어떻게 바로 값을 반영하는가? 그것은 자신이 대표 노드이므로 그 구간의 변화하는 노드의 수 또한 정보를 알 수 있기 때문에 구간 길이만큼 변경되는 값에 곱해서 더해주면 되는 것이다. ①의 과정은 이렇게 끝난다.

 

 

②의 과정을 보자

 

기존 lazy 값에 새로운 lazy값 반영!

 

자, 이번엔 5번 노드에 기존 lazy 값이 있었으므로 그에 대한 반영을 해주어야 하는데, 어라? +3만큼을 또 업데이트 해야 하니 도합 8만큼을 업데이트 한 뒤에 자식 노드에 lazy를 전파시키는 방식으로 진행된다.

기존에 arr[5] / arr[6]은 아직 탐색하지 않으니 그대로 lazy 값만 갖고 있는다.

실제로 코드 상으로는 업데이트를 먼저 하고 lazy를 또 다시 반영하는 방식으로 수행되지만 어쨋든 결과는 같으니 이렇게 이해해도 무방하다.(코드를 보면 이해할 수 있을 것이다.)

 

 

자, 이제 ③의 과정을 보자.

전체 구간을 대표하는 1번 노드만 탐색!

 

어라, 잠깐? lazy를 아래쪽으로 전파시켰는데 생각해보니 전파되는 대표노드의 부모 노드에는 반영이 안되고 있었던 것이 아닌가? 위로도 전파를 시켜야 온전히 전체 구조를 유지할 수 있게 되는 것이 아닐까?

바로 그렇다. 하지만 이는 매우 간단히 해결할 수 있다. 잘 생각해보면, 세그먼트 트리의 구조는 부모를 거쳐 자식을 탐색하기 때문에 재귀적인 성격을 갖고 있다.

그래서, 업데이트 시에 lazy를 반영한 뒤 재귀로 빠져나오기 전에 부모 노드에 자식 노드들의 합을 다시 입력해주면 간단히 해결되는 것이다.

 

이 모든 내용을 코드로 구현해보자. 일부 이해가 안되는 부분이 있다면 코드와 위 내용을 다시 번갈아가면서 이해해보도록 하자.

전체 코드는 아래와 같다.

package com.test;

public class SegmentTree{
    int size;
    long[] tree;
    long[] lazy;

    public SegmentTree(int n){
        int h = (int) Math.ceil(Math.log(n) / Math.log(2));
        this.size = (int)Math.pow(2, h+1);
        this.tree = new long[size];
        this.lazy = new long[size];
    }

    // 전체 Segment Tree를 만드는 메소드. 느린 전파 이전과 동일!
    public long init(long[] nums, int node_idx, int start, int end){
        if(start == end){
            return tree[node_idx] = nums[start];
        }
        int mid = (start+end)/2;
        return tree[node_idx] = init(nums, node_idx*2, start, mid) +
           init(nums, node_idx*2+1, mid+1, end);
    }

    // 느린 전파를 실제로 수행하는 메소드!
    private void lazy_update(int node_idx, int start, int end){
        // 만약 현재 노드에 lazy 정보가 없다면! 반환
        if(lazy[node_idx] == 0){
            return;
        }
        
        // 있으면 구간의 길이 * lazy 값 반영!
        tree[node_idx] += ((end - start +1) * lazy[node_idx]);
        if(end != start){
            lazy[node_idx * 2] += lazy[node_idx];
            lazy[node_idx * 2 + 1] += lazy[node_idx];
        }
        
        // 반영 후 0으로 다시 초기화
        lazy[node_idx] = 0;
    }

    public void update(int node_idx, int start, int end, int left, int right, long diff){
        // 각 대표 노드에 갈 때마다 lazy가 있는지 확인하여 업데이트
        lazy_update(node_idx, start, end);
        if(right < start || left > end){
            return;
        }

        // diff값이 lazy 이므로 현재 노드에 전달
        if(left <= start && end <= right){
            lazy[node_idx] += diff;
            lazy_update(node_idx, start, end);
            return;
        }
        update(node_idx * 2, start, (start+end)/2, left, right, diff);
        update(node_idx*2+1, (start+end)/2+1, end, left, right, diff);
        
        // 이것이 바로 위로 다시 전파하는 코드. 부모 노드에도 update가 전달됨
        tree[node_idx] = tree[node_idx * 2] + tree[node_idx*2+1];
    }

    public long sum(int node_idx, int start, int end, int left, int right){
        // 업데이트 후, sum을 하기 전에 lazy가 있다면 또 업데이트를 해야함!
        lazy_update(node_idx, start, end);
        if(left > end || right < start){
            return 0;
        }

        if(left <= start && end <= right){
            return tree[node_idx];
        }

        return sum(node_idx*2, start, (start+end)/2, left, right) +
           sum(node_idx*2+1, (start+end)/2+1, end, left, right);
    }
}

 

참고자료

멍멍멍님의 블로그 : bowbowbow.tistory.com/4

Segment Tree and Lazy Propagation

 

관련 문제 : 백준 10999번

www.acmicpc.net/problem/10999

 

 

 

오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.