세그먼트 트리는 모든 부분 구간에서의 값을 미리 계산해둔 트리이다. 따라서 어느 특정 구간의 계산값을 구하고자 할 때, 트리의 높이 정도의 값들만 가지고 최종 값을 도출할 수 있을 때 쓴다.
여기서는 최솟값 세그먼트 트리여서 트리에 최솟값만 저장하면 되지만, 필요하면 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 |