[자료구조] 백준 14438번: 수열과 쿼리 17 (C++)

https://www.acmicpc.net/problem/14438

14438번: 수열과 쿼리 17

업데이트를 하는 부분에서 문제가 있었는데 leaf 노드에서 value값을 새롭게 할당하고,

(start <= index && index <= end) 부분에서는 건드리면 안 된다.

저 조건에서 sgTree[node] = min(sgTree[node], value);를 달아주었는데 이전의 값과 현재 들어오는 값을 비교하는 건 value가 sgTree[node]보다 작지 않은 이상 작동하지 않는다.

>> 즉, leaf노드만 새로운 값으로 할당 시키고 나머지는 update를 시켜주면 된다.

int update(int start, int end, int node, int index, int value) {
	if (index < start || index > end) return sgTree[node];
	if (start == end) {
		return sgTree[node] = value;
	}
	int mid = (start + end) / 2;
	return sgTree[node] = min(
	update(start, mid, node * 2, index, value),
	update(mid + 1, end, node * 2 + 1, index, value));
}

[AC 코드]

#include <iostream>
#define MAX (100000 + 1)
#define INF 1000000000 + 1
using namespace std;

int arr[MAX];
int sgTree[MAX * 4];
int n, m;

int sgInit(int start, int end, int node) {
	if (start == end) {
		return sgTree[node] = arr[start];
	}
	int mid = (start + end) / 2;
	return sgTree[node] = min(sgInit(start, mid, node * 2),
		sgInit(mid + 1, end, node * 2 + 1));
}

int update(int start, int end, int node, int index, int value) {
	if (index < start || index > end) return sgTree[node];
	if (start == end) {
		return sgTree[node] = value;
	}
	int mid = (start + end) / 2;
	return sgTree[node] = min(
	update(start, mid, node * 2, index, value),
	update(mid + 1, end, node * 2 + 1, index, value));
}

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	sgInit(1, n, 1);
	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			update(1, n, 1, b, c);
			arr[b] = c;
		}
		else {
			cout << query(1, n, 1, b, c) << '\n';
		}
	}
	return 0;
}