백준 2357번 최솟값과 최댓값 C++ 세그먼트 트리

리뷰

세그멘트 트리를 사용하여 최솟값과 최댓값을 찾는 문제

 

문제 풀이

1. n, m값을 받고 tree_min과 tree_max를 각각 4 * n 크기르 초기화를 해준다.
2. 정수형 벡터 nodes를 초기화 하고 n개의 수를 해당 벡터에 push 해준다.
3. build_min, build_max 함수를 통해 nodes 벡터를 각각 tree_min, tree_max에 build 해준다.
4. update 해주는 경우는 없기 때문에 입력 받은 index에 맞게 query_min, query_max 함수를 실행해 주면 된다.

 

참고 사항

각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다 라는 조건이 있기 때문에 최소값 쿼리 함수의 범위가 벗어난 케이스는 1000000001을 리턴해 주고, 최대값 쿼리 함수의 범위가 벗어난 케이스는 0을 리턴해 주면 된다.

 

 

정답 코드

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

using namespace std;

int n, m;
vector<int> tree_min;
vector<int> tree_max;

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

int query_min(int node, int start, int end, int left, int right) {
    if (right < start || end < left) {
        return 1000000001;
    }
    if (left <= start && end <= right) {
        return tree_min[node];
    }
    int mid = (start + end) / 2;
    int left_min = query_min(2 * node, start, mid, left, right);
    int right_min = query_min(2 * node + 1, mid + 1, end, left, right);
    return min(left_min, right_min);
}

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

int query_max(int node, int start, int end, int left, int right) {
    if (right < start || end < left) {
        return 0;
    }
    if (left <= start && end <= right) {
        return tree_max[node];
    }
    int mid = (start + end) / 2;
    int left_max = query_max(2 * node, start, mid, left, right);
    int right_max = query_max(2 * node + 1, mid + 1, end, left, right);
    return max(left_max, right_max);
}

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

    cin >> n >> m;
    vector<int> nodes;
    tree_min.resize(4 * n);
    tree_max.resize(4 * n);
    
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        nodes.push_back(temp);
    }
    build_min(nodes, 1, 0, n - 1);
    build_max(nodes, 1, 0, n - 1);

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