(알고리즘) 구간트리 RMQ

struct RMQ
{
int n;
vector<int> rangeMin;
RMQ(int *arr)
{
n = N;
rangeMin.resize(N * 4);
init(arr, 0, 1, N - 1);
}
int init(int *arr, int left, int node, int right)
{
if (left == right)return rangeMin[node] = arr[left];

int mid = (left + right) / 2;

int leftMin = init(arr, left, node * 2, mid);
int rightMin = init(arr, mid + 1, node * 2 + 1, right);

return rangeMin[node] = min(leftMin, rightMin);
}
int query(int left, int right, int leftNode, int rightNode, int node){
if (right < leftNode || left >rightNode)return 999999;

if (left<=leftNode && right>=rightNode)return rangeMin[node];

int mid = (leftNode + rightNode) / 2;

return min(query(left, right, leftNode, mid, node * 2), query(left, right, mid + 1, right, node * 2 + 1));
}

int query(int left, int right)
{
return query(left, right, 0, N - 1, 1);
}

};