- init 만 보면 된다.
- 받는 배열의 index는 1부터 시작한다.
- 여기서 init안의 left는 0부터 시작하므로 받는 배열의 0번에는 0이 저장되어 있는데 init 함수가 재귀로 돌면서 이 값까지 처리한다.
- query로 찾을 때 답에는 영향이 없는데 최상위 노드에는 0이 저장된다.
- 이경우 left를 1로 바꾸면 최상위 노드가 5가된다.
- segment트리는 힙처럼 왼쪽 맨 아래부터 채워지는 게 아니라 다른 방식으로 채워진다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
using namespace std;
struct RMQ {
int n;
vector<int> rangeMin;
RMQ(const vector<int>& arr) {
n = arr.size();
rangeMin.resize(4 * n);
init(arr, 0, n - 1, 1);
}
int init(const vector<int>& arr, int left, int right, int node) {
if (left == right) {
return rangeMin[node] = arr[left];
}
int mid = (left + right) / 2;
int leftMin = init(arr, left, mid, 2 * node);
int rightMin = init(arr, mid + 1, right, 2 * node + 1);
return rangeMin[node] = min(leftMin, rightMin);
}
int query(int left, int right, int node, int nodeLeft, int nodeRight) {
if (right < nodeLeft || left > nodeRight) {
return INT32_MAX;
}
if (left <= nodeLeft && right >= nodeRight) {
return rangeMin[node];
}
int mid = (nodeLeft + nodeRight) / 2;
int leftbaby = query(left, right, node * 2, nodeLeft, mid);
int rightbaby = query(left, right, node * 2 + 1, mid + 1, nodeRight);
return min(leftbaby, rightbaby);
}
int query(int left, int right) {
return query(left, right, 1, 0, n - 1);
}
int update(int index, int newValue, int node, int nodeLeft, int nodeRight) {
//index가 범위와 관계없을 경우
if (index < nodeLeft || index > nodeRight) {
return rangeMin[node];
}
//리프까지 내려온 경우
if (nodeLeft == nodeRight) {
return rangeMin[node] = newValue;
}
int mid = (nodeLeft + nodeRight) / 2;
int a = update(index, newValue, 2 * node, nodeLeft, mid);
int b = update(index, newValue, 2 * node + 1, mid + 1, nodeRight);
return rangeMin[node] = min(a, b);
}
int update(int index, int newValue) {
return update(index, newValue, 1, 0, n - 1);
}
};
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<int> input(n+1);
for (int i = 1; i <= n; ++i) {
cin >> input[i];
}
RMQ myRMQ(input);
int cnt = 1;
int first_2 = 2;
//for (int i = 1; i < myRMQ.rangeMin.size(); ++i) {
//
// cout << myRMQ.rangeMin[i] << ' ';
// cnt++;
// if (cnt == first_2) {
// cout << endl;
// first_2 *= 2;
// }
//}
int a, b;
for (int i = 0; i < m; ++i) {
cin >> a >> b;
cout << myRMQ.query(a, b) << '\n';
}
return 0;
}