백준 10868번 최솟값 C++ 세그먼트 트리

리뷰

세그먼트 트리를 활용해 구간 내 최솟값을 찾는 문제

 

문제 풀이

1. n, m값을 입력 받고 정수형 벡터 nodes를 초기화 하고 정수형 벡터 tree를 4 * n크기로 초기화 한다.
2. n개의 줄로 입력되는 정수를 nodes 벡터에 푸시 해주고 nodes를 바탕으로 tree를 build 해준다.
3. update를 해주는 경우는 없으므로 query를 통해 b - 1 ~ c - 1범위를 탐색하여 최소값을 출력해 주면 된다.

 

참고 사항

각각의 정수는 1,000,000,000 이하의 값을 가지므로 query 탐색 시 범위 조건에 맞지 않는 경우 1000000001를 리턴해 준다.

 

 

정답 코드

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

using namespace std;

int n, m;
vector<int> tree;

void build(vector<int>& nodes, int node, int start, int end) {
    if (start == end) {
        tree[node] = nodes[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;
    }
    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 1000000001;
    }
    if (left <= start && end <= right) {
        return tree[node];
    }
    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 >> m;
    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);

    while (m--) {
        int b, c;
        cin >> b >> c;
        cout << query(1, 0, n - 1, b - 1, c - 1) << "\n";
    }
}