백준 14438번 수열과 쿼리 17 C++ 세그먼트 트리

리뷰

세그먼트 트리를 활용하여 최소값을 구하는 문제

 

문제 풀이

상세 내용은 https://zzzz955.tistory.com/180를 참고 바란다.

위 링크 문제에서 index가 아닌 최소 값을 구하는 문제, 폼은 거의 일치하며 오히려 더 쉬운 문제다.

 

 

참고 사항

없음

 

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> tree;

void build(vector<int>& lst, int node, int start, int end) {
	if (start == end) {
		tree[node] = lst[start];
	}
	else {
		int mid = (start + end) / 2;
		build(lst, node * 2, start, mid);
		build(lst, node * 2 + 1, mid + 1, end);
		tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
	}
}

void update(int node, int start, int end, int idx, int val) {
	if (start == end) {
		tree[node] = val;
	}
	else {
		int mid = (start + end) / 2;
		if (start <= idx && idx <= mid) {
			update(node * 2, start, mid, idx, val);
		}
		else {
			update(node * 2 + 1, mid + 1, end, idx, val);
		}
		tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
	}
}

int query(int node, int start, int end, int L, int R) {
	if (R < start || end < L) {
		return 1000000001;
	}
	if (L <= start && end <= R) {
		return tree[node];
	}
	int mid = (start + end) / 2;
	int left = query(node * 2, start, mid, L, R);
	int right = query(node * 2 + 1, mid + 1, end, L, R);
	return min(left, right);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	vector<int> lst(n);
	tree.resize(n * 4);
	for (int i = 0; i < n; i++) {
		cin >> lst[i];
	}
	build(lst, 1, 0, n - 1);
	cin >> m;
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) update(1, 0, n - 1, b - 1, c);
		else cout << query(1, 0, n - 1, b - 1, c - 1) << "\n";
	}
}