본문 바로가기

세그먼트 트리 ( 구간 최소값 preprocessing )

세그먼트 트리는 모든 부분 구간에서의 값을 미리 계산해둔 트리이다. 따라서 어느 특정 구간의 계산값을 구하고자 할 때, 트리의 높이 정도의 값들만 가지고 최종 값을 도출할 수 있을 때 쓴다.


여기서는 최솟값 세그먼트 트리여서 트리에 최솟값만 저장하면 되지만, 필요하면 pair 등을 사용해서 최소값 2개의 값이나 그 구간의 최대반복수 등을 기록해서 재귀단계별로 프로세싱 해도 되겠다.


init 재귀의 시간 복잡도 : 2*n+2 번의 init을 호출하고 각각은 O(1) 이므로 전체는 O(N)

findmin의 시간 복잡도 : 바이너리 서치와 같은 O(logN)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int init(vector<int> & data, vector<int> & segtree, int high, int low, int node) {
    // base case
    if (low == high) {
        segtree[node] = data[low];
        return data[low];
    }
    // general case
    int mid = (low + high) / 2;
    int left = init(data, segtree, mid, low, 2 * node + 1);
    int right = init(data, segtree, high, mid + 1, 2 * node + 2);
    segtree[node] = min(left, right);
    return segtree[node];
}
 
void preprocess(vector<int> & data, vector<int> & segtree) {
    segtree.resize(data.size() * 4);
    for (int i = 0; i < segtree.size(); i++) {
        segtree[i] = INT_MAX;
    }
    init(data, segtree, data.size()-1,0, 0);
}
 
int findmin(vector<int> & segtree, int low, int high, int clow, int chigh, int curr) {
    // base case
    if (low == clow && high == chigh) return segtree[curr];
    // general case
    int mid = (clow + chigh) / 2;
    if (low <= mid&& high >= mid + 1) {
        return min(findmin(segtree, low, mid, clow, mid, curr * 2 + 1), findmin(segtree, mid + 1, high, mid + 1, chigh, curr * 2 + 2));
    }
    else if (high <= mid) {
        return findmin(segtree, low, high, clow, mid, curr * 2 + 1);
    }
    else {
        return findmin(segtree, low, high, mid + 1, chigh, curr * 2 + 2);
    }
}
 
int findmin2(vector<int> & segtree, int low, int high, int m) {
    return findmin(segtree, low, high, 0, m-1, 0);
}
 
int main() {
    vector<int> v1 = { 1,3,2,7,9,11 };
    vector<int> segtree;
    preprocess(v1, segtree);
    for (int x : segtree) cout << x << " ";
    cout << endl;
    cout << findmin2(segtree, 1, 5, v1.size()) << endl;
    while(1){}
    return 0;
}
cs


'' 카테고리의 다른 글

세그먼트 트리 ( 구간 최소값 preprocessing )  (0) 2018.04.17
Heap 구현  (0) 2018.04.15
Binary Heaps  (0) 2018.04.15
priority queue(max heap)  (0) 2018.03.25
when to use STL data structures(multimap)  (0) 2018.03.25
data structures  (0) 2018.03.24