[baekjoon 14438] 수열과 쿼리 17 - 세그먼트 트리

 

www.acmicpc.net/problem/14438

 

14438번: 수열과 쿼리 17

기본적인 세그먼트 트리 문제.

최근에 전공 기말프로젝트 하느라 문제를 못풀었더니 바로 풀리진 않았다.

함수는 init, 구간의 최솟값을 저장해주는 minTree, update 함수로 구성하였다.

update함수를 구현할때 diff값을 이용해서 (기존 값 - 변경하려는 값) 했었는데

곱셈이나 나눗셈 등 애매한 경우가 있어서 아예 target index를 찾아서 리프노드의 값을 변경해주는 식으로 짜고 있다.

 

이런 식으로 리프노드 자체를 바꿔주면 값을 저장하는 배열을 매번 업데이트 해줘야 할 필요도 없고

리프노드에서부터 구간의 최솟값을 저장한다는 개념이 더 직관적으로 다가오는 것 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int Init(vector<int>& arr, vector<int>& tree, int node, int start, int end) {
	int r = (start + end) / 2;
	if (start == end) {
		return tree[node] = arr[start];
	}
	else
		return tree[node] = min(Init(arr, tree, node * 2, start, r), Init(arr, tree, node * 2 + 1, r + 1, end));
}

int minTree(vector<int>& tree, int node, int start, int end, int left, int right) {
	int r = (start + end) / 2;
	
	if (left > end || right < start) {
		return 1000000001;
	}
	else if (left <= start && end <= right) {
		return tree[node];
	}
	else
		return min(minTree(tree, node * 2, start, r, left, right), minTree(tree, node * 2 + 1, r + 1, end, left, right));
}

int updateTree(vector<int>& tree, int node, int start, int end, int target, int updateNum) {
	int r = (start + end) / 2;
	if (target < start || target > end) { // 1차적으로 범위를 거르자
			return tree[node];
	}
	else if (start == end) { // 이 경우를 if문 먼저했더니 target index와 다른 경우에도 update가 되어서 다른 노드의 값도 update되어버렸다.
		return tree[node] = updateNum;
	}
	else
		return tree[node] = min(updateTree(tree, node * 2, start, r, target, updateNum), updateTree(tree, node * 2 + 1, r + 1, end, target, updateNum));
}

int N, M, a, b, c;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	vector <int> arr(N);
	int h = (int)ceil(log2(N));
	int size = 1 << (1 + h);
	vector <int> segmentTree(size);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	Init(arr, segmentTree, 1, 0, N - 1);
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
			updateTree(segmentTree, 1, 0, N - 1, b-1, c);
		}
		else {
			cout << minTree(segmentTree, 1, 0, N - 1, b-1, c-1) << "\n";
		}
	}
}

 

오늘의 피드백 :

 - 1. update함수를 구현할 때 아무 생각 없이 start == end 조건문을 먼저 쓰고

그 다음 target < start || target > end 구간비교를 했더니 start==end (리프노드도착) 했을 시

사실상 범위에서 벗어나서 관련없는 노드임에도 값이 update되버렸다.

index보다 크거나 작으면 변경되면 안되고 기존 값을 가지고 있어야 함으로.. 먼저 처리해주고 그 다음 비교하는 것이 맞다.

 - 2. 재귀로 함수를 구현하다보니 return을 종종 빼먹어버린다.. return 빼먹으면 값 전달 안되서 이상해진다..