[C/C++] 백준 #2357 최솟값과 최댓값(세그먼트 트리)

세그먼트 트리를 구현해서 푸는 문제가 참 많습니다.  옛날에는 세그먼트 트리가 Platinum 등급에 있었는데, 이제는 모두 Gold 등급으로 떨어졌습니다.

 

https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

 

최소값과 최대값을 주어진 범위안에서 찾는 알고리즘은 모두 \(O(N)\) 입니다.  미리 테이블을 만들어서 하는 것도 어렵죠.  세그먼트 트리만이 올바른 방법이라고 볼 수는 없습니다.  데이터를 \(\sqrt{N}\)씩 분할해서 그 안에서 최소값, 최대값을 저장해놓으면, 쿼리 한번에 \(O(\sqrt{N})\)으로 찾을 수도 있습니다.  하지만 세그먼트 트리를 이용하면, 세그먼트 트리를 만드는 비용이 \(O(N)\)이고, 쿼리를 한번 수행하는 것이 \(O(\log N)\)이므로 M개의 쿼리를 처리하는데 들어가는 시간복잡도는 \(O(N + M \log N)\)이 됩니다.

 

finding min and max values in a specific range

 

세그먼트 트리를 만드는 방법은 다음 게시물을 참고하세요.

https://sdev.tistory.com/512

[C/C++] 백준 #1275 커피숍2(세그먼트 트리)

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2357
//        - by Aubrey Choi
//        - created at 2019-11-07
//------------------------------------------------
#include <stdio.h>
#define    INF    1000000000

struct TValue { int min, max; };
TValue TInf={ INF, 0 };
//    Segment tree
class SegmentTree
{
public:
    SegmentTree(int n) {int s=1;while(s<n) s<<=1;tree = new TValue[s<<1];v = new int[n];}
    ~SegmentTree() { delete[] tree; delete[] v; }
    int MIN(int a, int b) { return a<b?a:b; }
    int MAX(int a, int b) { return a>b?a:b; }
    TValue &init(int c, int s, int e)
    {
        if(s+1==e) { tree[c].min=tree[c].max=v[s]; return tree[c]; }
        int m = (s+e)/2;
        TValue a = init(c*2, s, m), b = init(c*2+1, m, e);
        tree[c].min=MIN(a.min, b.min);
        tree[c].max=MAX(a.max, b.max);
        return tree[c];
    }
    TValue getMinMax(int c, int s, int e, int sc, int ec)
    {
        if(ec<=s||sc>=e) return TInf;
        if(sc<=s&&ec>=e) return tree[c];
        int m = (s+e)/2;
        TValue a=getMinMax(c*2,s,m,sc,ec), b=getMinMax(c*2+1,m,e,sc,ec), r;
        r.min = MIN(a.min, b.min);
        r.max = MAX(a.max, b.max);
        return r;
    }
    int operator [](const int i) { return v[i]; }
    TValue *getTree() { return tree+1; }
    int *getValue() { return v; }
private:
    TValue *tree;
    int *v;
};

int main()
{
    int n, m, a, b;
    scanf("%d%d", &n,&m);
    SegmentTree tree(n);
    int *v = tree.getValue();
    for(int i=0;i<n;i++) scanf("%d", v+i);
    tree.init(1, 0, n);
    while(m--)
    {
        scanf("%d%d",&a,&b);
        TValue c = tree.getMinMax(1, 0, n, a-1, b);
        printf("%d %d\n", c.min, c.max);
    }
}