세그먼트 트리 코드
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
const int INF = 1111111111;
void init(vector<int>& input, vector<int>& tree, int node, int start, int end){
if (start == end) {
tree[node] = input[start];
return;
}
init(input, tree, 2*node, start, (start+end)/2);
init(input, tree, 2*node+1, (start+end)/2+1, end);
tree[node] = min(tree[2*node], tree[2*node+1]);
return;
}
int findMin(vector<int>& tree, int node, int start, int end, int left, int right){
if (left > end || right < start) {
return INF;
} else if (left <= start && end <= right){
return tree[node];
}
int a = findMin(tree, 2*node, start, (start+end)/2, left, right);
int b = findMin(tree, 2*node+1, (start+end)/2+1, end, left, right);
return min(a, b);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, m;
cin >> n >> m;
int h = int(ceil(log2(n)))+1;
int treeSize = (1 << h);
vector<int> tree(treeSize, INF);
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
init(a, tree, 1, 0, n-1);
for (int i = 0; i < m; i++) {
int left, right;
cin >> left >> right;
cout << findMin(tree, 1, 0, n-1, left-1, right-1) << '\n';
}
}
Author And Source
이 문제에 관하여(세그먼트 트리 코드), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsvk9921/세그먼트-트리-코드저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)