24. 구간 트리

24.1 구간 트리: 구간에 대한 질문 대답하기

  • 이제 까지 다룬 트리들은 모두 자료들을 특정 순서대로 저장, 추가, 삭제하는 등 자료를 저장하는 용도로 사용
  • 구간 트리(segment tree) 는 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록 한다.
    • 흔히 일차원 배열의 특정 구간에 대한 질문을 빠르게 대답하는데 사용 ( 일반적인 접근 => O(N) )
    • 예시) 구간의 최소치
  • 기본적인 아이디어: 주어진 배열의 구간들을 표현하는 이진 트리를 만든다.
    • 구간 트리의 루트는 배열의 전체 구간 [0, n-1]을 표현
    • 왼쪽, 오른쪽 자식은 각각 해당 구간의 왼쪽 반과 오른쪽 반을 표현
    • 길이가 1인 구간을 표현하는 노드들은 구간 트리의 리프 노드가 된다.
  • 구간 트리는 노드마다 해당 구간에 대한 계산 결과를 저장해 둔다.
  • 이런 전처리 과정을 수행해 두면 어떤 구간 [i, j]가 주어지더라도 이 구간을 구간 트리의 노드에 포함된 구간들의 합집합으로 표현 가능
    • [6, 12] : [6, 7], [8, 11], [12, 12] 의 합집합
    • 원하는 답은 각 구간의 최소치(미리 계산됨, 이 셋 중의 최소치) 이다.
  • 어떤 구간이 주어지건 간에 답을 찾기 위해 우리가 고려해야 하는 구간의 수는 O(logN)이다.
    • 따라서, O(N) 대신, O(logN) 시간에 질의에 대답할 수 있게 된다.

image-20240408211015162.png

24.1.1 구간 트리의 표현

  • 구간 최소 쿼리(range minimum query, RMQ): 특정 구간의 최소치
  • 비교적 ‘꽉 찬’ 이진 트리로 표현 => 일차원 동적 배열로 표현 가능
    • 루트를 1번으로, i번째 를 부모, 2*i(왼쪽 자손), 2*i+1(오른쪽 자손)
    • 배열의 길이: 가장 가까운 2의 거듭제곱으로 n을 올림한 뒤 2를 곱함
      • 간단하게, n에 4를 곱해도 가능

24.1.2 구간 트리의 초기화

  • 초기화에서 각 노드마다 걸리는 시간은 O(1), 초기화 과정에는 노드의 수와 같은 시간이 걸린다.
  • 배열의 크기가 O(N)임으로, 노드의 수도 O(N)이다. 따라서 초기화 과정의 시간복잡도는 O(N)이다.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// 배열의 구간 최소 쿼리를 해결하기 위한 구간 트리의 구현
struct RMQ{
    int n;     // 배열의 길이
    vector<int> rangeMin; // 각 구간의 최소치
    RMQ(const vector<int>& array){
        n = array.size();
        rangeMin.resize(n * 4);
        init(array, 0, n-1, 1);
    }
    
    // node 노드가 array[left .. right] 배열을 표현할 때
    // node를 루트로 하는 서브트리를 초기화하고, 이 구간의 최소치를 반환한다.
    int init(const vector<int>& array, int left, int right, int node){
        if(left == right)
            return rangeMin[node] = array[left];
        int mid = (left + right) / 2;
        int leftMin = init(array, left, mid, node * 2);
        int rightMin = init(array, mid +1, right, node * 2 + 1);
        return rangeMin[node] = min(leftMin, rightMin);
    }
};

24.1.3 구간 트리의 질의 처리

  • query(left, right, node, nodeLeft, nodeRight) =

    node가 표현하는 범위 [nodeLeft, nodeRight]와 우리가 최소치를 찾기 원하는 구간 [left, right]의 교집합의 최소 원소를 반환하는 함수

  • query는 아래와 같은 3가지 경우에 놓이게 된다. (구간의 최소치를 찾는 질의의 경우)

    • 교집합이 공집합인 경우
      • 두 구간은 서로 겹치지 않는다.
      • 따라서 반환 값은 존재하지 않는다.
      • 반환 값이 무시되도록 아주 큰 값을 반환.
    • 교집합이 [nodeLeft, nodeRight]인 경우
      • [left,right]가 노드가 표현하는 집합을 완전히 포함하는 경우
      • 이 노드에 미리 계산해 둔 최소치를 곧장 반환.
    • 이 외의 모든 경우
      • 두 개의 자손 노드에 대해 query()를 재귀 호출한 뒤, 이 두 값 중 더 작은 값을 택해 반환합니다.

image-20240408211423129.png

24.1.4 구간 트리의 갱신

  • 전처리를 통해 구간 트리를 생성한 다음에, 원래 배열의 값이 바뀐 경우에 대한 갱신(update) 을 진행
  • 원래 배열의 index 위치의 값이 newValue로 바뀌었다고 하자.
    • 이 위치를 포함하는 구간은 트리에 O(logN)개 존재
    • 이들만을 재계산하면 O(logN)시간에 구간트리를 갱신할 수 있습니다.

24.4 트리의 최소 공통 조상 찾기 (LCA), 족보 탐험 문제

  • 두 노드의 최소 공통 조상(least/lowest common ancestor, LCA)
  • 트리에서 두 노드 u,v의 최소 공통 조상(u,v) // LCA(u, v)는 두 노드를 모두 자손으로 갖는 노드 중 가장 아래 있는 노드이다.

24.4.1 트리를 일렬로 펴기

image-20240408220226016.png

  • 구간 트리는 일렬로 늘어선 배열을 처리하는 자료 구조이므로,
    • 구간 트리를 사용하려면 트리를 쭉 ‘펴서’ 일렬로 만들어야 한다.
  • 구현하는 방법은 트리를 전위 순회하면서 방문하는 노드들을 순서대로 늘어놓는 것
    • 단, 재귀 호출이 끝나고 이전 노드로 돌아오는 것도 노드를 방문하는 것으로 쳐야 한다.

  • 전위 순회 결과 Path = {0, 1, 2, 1, 3, 4, 3, 5, 3, 1, 0, 6, 7, 6, 0, 8, 9, 10, 9, 11, 9, 8, 12, 8, 0}

  • 이 경로(전체 경로의 길이)의 길이는?

    • 이 경로는 부모와 자식 간의 각 연결을 정확히 한 번씩 내려가고 한 번씩 올라온다.

    • 트리에는 항상 n-1개의 연결(edge)이 있으므로, 2n-2번 움직인다.

    • 루트에서 시작하므로 +1, 전체 경로의 길이는 2n-1이 됩니다.

  • 어떤 노드 u에서 시작해서 다른 노드 v에서 끝나는 부분 경로를 떼어냈을 때, 이 경로가 방문하는 최상위 노드는 항상 u와 v의 최소 공통 조상이다.

  • 즉, u와 v는 항상 LCA(u,v)의 서로 다른 서브트리에 포함되어 있다는 점을 이용해 설명 가능

    • u를 포함하는 서브트리에서 v를 포함하는 서브트리로 넘어가려면 LCA(u,v)를 거치지 않으면 안 된다.

      • 따라서 LCA(u,v)는 항상 방문

    • LCA(u,v)에서 그 부모 노드로 이 경로가 올라가려면, 그 전에 LCA(u,v)를 루트로 하는 서브트리를 모두 돌아본 후여야 한다.

      • 따라서 LCA(u,v)의 조상 노드들을 u와 v사이에 방문하는 일은 없다.
  • 이 문제는 P에서 u의 위치와 v의 위치가 주어질 때, 이 구간에서 가장 상위에 있는 노드는 무엇인가를 묻는 문제로 접근 가능

24.4.2 특정 구간에서 최상위 노드 찾기

  • 최소 질의를 위한 구간 트리를 사용
    • 상위에 있는 노드일수록 더 작은 번호를 갖도록 각 노드들의 번호를 다시 매긴다.
    • 각 서브트리의 루트에 가장 먼저 번호를 매기기 때문에, 자손들의 번호는 항상 부모의 번호 뒤에 온다.

24.4.3 주어진 문제 풀기

  • 이제 LCA질의는 시간복잡도는 O(logN)으로 해결 가능
  • 두 사람 사이의 경로의 길이는 구하는 방법
    • u 에서 LCA(u, v) 까지 : depth[u] - depth[LCA(u,v)]
    • LCA(u, v)에서 v까지 : depth[v] - depth[LCA(u,v)]
  • 문제에서 원하는 두 사람 사이의 경로의 길이
    • depth[u] + depth[v] - 2 * depth[LCA(u,v)]

24.6 펜윅 트리: 빠르고 간단한 구간 합

  • 구간 트리의 가장 흔한 사용 예는 바로 구간 합(prefix sum) 을 빠르게 구하는 것

    • 이 경우 구간 트리 대신, 펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(binary indexed tree) 라고 불리 우는 것을 사용할 수 있다.

  • 중간에 배열의 원소의 값이 갱신(update) 되어도, O(logN)에 수행할 수 있다.

    • ch17에서 다룬 부분합 알고리즘을 이용할 수도 있지만, 이 경우 배열의 원소의 갱신(update) 하는 연산에 시간이 오래 걸린다.

  • 구간 합 대신 부분 합(partial sum, psum) 만을 빠르게 계산할 수 있는 자료 구조를 만들어도, 구간 합을 계산할 수 있다는 것

  • psum[pos] = A[0] + A[1] + … + A[pos]를 빠르게 구할 수 있으면,

  • 구간 [i ,j]에 대한 합은 psum[j] - psum[i]로 계산할 수 있다.

  • 부분 합만을 계산한다고 생각하면, 구간 트리가 미리 계산해 저장하는 정보의 상당수는 필요가 없다.

    • 하나의 긴 구간 밑에 두 개의 작은 구간이 있을 때, 이 두 구간 중 왼쪽 구간만 필요 (오른쪽은 지워도 된다.)

  • 오른쪽을 지우고, 남은 구간의 갯수는 정확하게 N이다.

    • N개의 수에 대한 부분 합을 N개의 숫자에 저장

image-20240408220501233.png

  • 펜윅 트리는 이 대응을 이용해 1차원 배열 하나에 각 구간의 합을 저장합니다.
    • 배열 tree[]: tree[i] = 그림(b) 에서 오른쪽 끝 위치가 A[i]인 구간의 합
  • A[pos] 까지의 구간 합 // psum[pos]를 계산하고 싶으면
    • 그림(b)에서 pos에서 끝나는 구간의 합, tree[pos] 를 답에 더한다.
    • 남은 부분들은 왼쪽에서 찾아서 더한다.
    • psum[12] === tree[12] + tree[11] + tree[7]
    • 어떤 부분 합을 구하든 O(logN) 개의 구간 합만 있으면 된다.

24.6.1 펜윅 트리의 구현

image-20240408220434137.png

Reference