백준 - 수열과 쿼리 17 (14438) [C++]

이 문제는 세그먼트 트리 연습 문제이다.

 

이 문제에서 조심할 점은 update 시 만약 수정할 index가 start ~ end 범위에 맞지 않을 때, segment[node]를 리턴하는 것이다.

나는 여기서 INF를 리턴하도록 했었는데, 이런 식으로 하면 오답이 나온다.

 

또한 단순히 void update로 선언하여 합일 때의 코드처럼 짜면 정답이 나오지 않게 된다. 단순히 index가 start ~ end 범위 안에 있을 때

segment[node] = min(segment[node], to) 이런 식으로 구현하게 되면 당연히 수정되지 않는다.

이유는 기존 값이 바뀌는 값보다 작은 경우 갱신되지 않기 때문이다. 따라서 이 문제를 방지하기 위해서는 update가 init 함수와 비슷한

형태를 취하도록 변경해야 문제를 풀 수 있다.

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

#define MAX 100000
#define INF 1000000001

int input[MAX + 1];
int segment[MAX * 4 + 1];
int N, M;

int init(int node, int start, int end) {
    if (start == end) {
        return segment[node] = input[start];
    }

    int mid = (start + end) / 2;
    int left = init(node * 2, start, mid);
    int right = init(node * 2 + 1, mid + 1, end);

    return segment[node] = min(left, right);
}

int findMin(int node, int start, int end, int left, int right) {
    if (end < left || start > right) {
        return INF;
    }

    if (left <= start && end <= right) {
        return segment[node];
    }

    int mid = (start + end) / 2;
    int leftMin = findMin(node * 2, start, mid, left, right);
    int rightMin = findMin(node * 2 + 1, mid + 1, end, left, right);

    return min(leftMin, rightMin);
}

int update(int node, int start, int end, int index, int to) {
    if (index < start || index > end) {
        return segment[node];
    }

    if (start == end) {
        if (start == index) {
            return segment[node] = to;
        }
        return INF;
    }

    int mid = (start + end) / 2;
    
    int left = update(node * 2, start, mid, index, to);
    int right = update(node * 2 + 1, mid + 1, end, index, to);

    return segment[node] = min(left, right);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> input[i];
    }

    init(1, 1, N);

    cin >> M;
    for (int j = 0; j < M; j++) {
        int a, b, c;

        cin >> a >> b >> c;
        if (a == 1) {

            input[b] = c;
            update(1, 1, N, b, c);
        } else {
            cout << findMin(1, 1, N, b, c) << '\n';
        }
    }

    return 0;
}