세그먼트 트리(Segment Tree)

세그먼트 트리

구간에 대한 정보를 저장하기 위한 트리 자료구조 O(N logN)

  N == 8일 때 Segment Tree

  특정 구간의 최적화된 답을 구하는 문제인 경우 빠른 시간안에 답을 얻을 수 있음

  (ex. 구간의 합, 최대값, 최소값, 곱)

 

N == 5일 때 Segment Tree

- 완전 이진트리 형태 (Root Node의 인덱스가 1번인경우 보다 쉽게 자식노드에 접근 가능)

   : 재귀적인 구조로 구현을 많이 합니다.

- 전체 구간이 [0, N-1]일 때, 단말 노드는 구간 길이 1인 구간을 갖습니다.

  → 배열 = [a, b, c, d, e]가 있을 때 단말노드(Leaf Node)에 배치된다고 보면 됩니다.

  * 트리에서 실제 노드번호는 N의 크기에 따라 좌우되기 때문에 단말노드 번호를 쉽게 알 수 없습니다.

시간 복잡도 O(logN) 

 

※ 세그먼트 트리를 활용하기 위해서는 트리의 구조를 기본적으로 이해하되

    단말노드에 어떤 데이터를 설정할지, 구간의 어떤 값을 구할 지 설계해야 합니다.

 

구현할 때, n번 노드는 [s, e] 구간 정보를 갖고 있음

노드의 구간 s == e일 경우 : 단말 노드(Leaf Node)

 

트리 구성은 1번 노드부터 시작하지만

단말 노드에서는 0번부터 트리를 구성한다고 봐야 됩니다.

 

구현

[update]

void update(int tree[], int now, int s, int e, int pos, int val) {
    if (s == e) {
        tree[now] = val;
        return;
    }
    int L = now * 2, R = L + 1, mid = (s + e) / 2;
    if (pos <= mid) update(tree, L, s, mid, pos, val);
    else update(tree, R, mid + 1, e, pos, val);
    tree[now] = tree[L] + tree[R];
}

　

[query]

int query(int tree[], int now, int s, int e, int qs, int qe) {
    if (e < qs || qe < s) return 0;
    if (qs <= s && e <= qe) return tree[now];
    int L = now * 2, R = L + 1, mid = (s + e) / 2;
    return query(tree, L, s, mid, qs, qe) + query(tree, R, mid + 1, e, qs, qe);
}