백준 10868, Segment Tree
solved.ac를 활용한 랜덤 복습 문제.
Segment Tree 에 입문하는 기본 문제다. 원리를 제대로 기억하니까 구현도 한 번에 성공했다.
Segment Tree 의 핵심은 구간을 설정하는 방법이다.
init(left,right,node) 는 left 와 right 구간을 표시하는 node 일때,
$[left : right]$ 구간에서 가장 작은 값을 tree[node] 에 저장하여 segtree 전체를 초기화 한다.
query(left,right,node,nodeLeft,nodeRight) 는 원하는 구간 left, right 가 주어졌을때,
$[left : right]$ 구간에서 가장 작은 원소를 return 한다.
각 node 가 표시하는 구간은 미리 정해져 있기 때문에, node가 표시하는 구간이 left 와 right 사이에 포함 되어있는지 확인하면 된다.
Source Code
// BOJ10868
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define Msize 100100
#define ll long long
ll input[100100];
int N, Q;
struct segtree {
ll tree[4 * Msize];
segtree() {
memset(tree, 0, sizeof(tree));
}
ll init(int left, int right, int node) {
//init(1,N,1)
if (left == right) {
tree[node] = input[left];
return tree[node];
}
int mid = (left + right) / 2;
tree[node] = min(init(left, mid, node * 2), init(mid + 1, right, node * 2 + 1));
return tree[node];
}
ll query(int left, int right, int node, int nodeLeft, int nodeRight) {
//query(left,right,1,1,N);
if (left > nodeRight || right < nodeLeft) return LLONG_MAX;
// 만약 node 가 표시하는 구간이 left 와 right 사이에 없다면 return MAX.
if (left <= nodeLeft && right >= nodeRight) return tree[node];
// 만약 node 가 표시하는 구간이 left 와 right 사이에 포함 된다면 node 의 값을 return.
int mid = (nodeLeft + nodeRight) / 2;
return min(query(left, right, node * 2, nodeLeft, mid), query(left, right, node * 2 + 1, mid + 1, nodeRight));
// 만약 node 가 표시하는 구간이 left 와 right 구간과 일부만 겹친다면 구간을 쪼갠다.
}
};
segtree SEG;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> Q;
for (int i = 0; i < N; ++i) {
cin >> input[i + 1];
}
SEG.init(1, N, 1);
for (int i = 0; i < Q; ++i) {
int s, e;
cin >> s >> e;
printf("%lld\n", SEG.query(s, e, 1, 1, N));
}
return 0;
}