백준 14427번 수열과 쿼리 15 C++ 세그먼트 트리

리뷰

세그먼트 트리를 공부하며 실습용으로 선택한 문제, 이제 슬슬 C++에서도 입출력을 신경 써줘야 할때가 온 것 같다.

 

문제 풀이

1. 배열의 크기와 배열을 받아와 주고 4 * n크기로 트리를 초기화 해준다. 
2. 받아온 배열로 세그먼트 트리를 최소값 형식으로 build 해준다.
3. 이후 m을 입력 받고 m크기 만큼 루프를 실행해 준다.
4. order값이 2일 경우 최소값을 출력하는 query를 실행해 준다.
5. order값이 1일 경우 트리의 i - 1번째 요소를 v로 바꿔준다.

 

참고 사항

m이 최대 10만이므로 ios::sync_with_stdio(false); cin.tie(NULL);로 입력 속도를 최적화 해주니 통과하였다.

인덱스도 사용해야 하니 세그먼트 트리를 pair<int, int> 형식으로 초기화 하였다. 첫번째 정수는 노드 번호, 두번째 정수는 인덱스를 나타내주면 된다.

INT_MAX 사용을 위해 climits도 추가해 줘야 한다. 처음에 추가해주지 않아 컴파일 에러가 났다.

 

정답 코드

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int n, m;
vector<pair<int, int>> tree;

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

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

int query(int node, int start, int end, int left, int right) {
    if (right < start || end < left) {
        return INT_MAX;
    }
    if (left <= start && end <= right) {
        return tree[node].second;
    }
    int mid = (start + end) / 2;
    int left_min = query(2 * node, start, mid, left, right);
    int right_min = query(2 * node + 1, mid + 1, end, left, right);
    return min(left_min, right_min);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    vector<int> nodes;
    tree.resize(4 * n);
    
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        nodes.push_back(temp);
    }
    build(nodes, 1, 0, n - 1);

    cin >> m;
    while (m--) {
        int order;
        cin >> order;
        if (order == 2) {
            cout << query(1, 0, n - 1, 0, n - 1) + 1 << "\n";
        }
        else {
            int id1, id2;
            cin >> id1 >> id2;
            update(1, 0, n - 1, id1 - 1, id2);
        }
    }
}