BOJ 10868 최솟값

📝 문제 정보

링크: https://www.acmicpc.net/problem/10868

🧐 관찰 및 접근

구간 최솟값을 $M$번 구하는 문제이다.
구간합은 누적합 배열을 이용해서 $O(1)$에 구할 수 있다.
- 하지만 구간 최솟값은 역원과 역연산이 없기에, 누적 최솟값 배열을 이용하기 곤란하다.
세그먼트 트리를 이용해서 구간 $O(logN)$개의 구간만을 관리하는 방법으로 풀 수 있겠다.
하지만, 업데이트가 없는 경우 희소 배열을 이용해서 $O(1)$에 구할 수 있음이 알려져있다.

💻 풀이

코드 (C++):

struct RMQ{ // Range Minimum Query
    int N, H;
    vector<vector<int>> table;

    RMQ(int N, vector<int> &arr): N(N){
        H = 1;
        while((1 << H) <= N) H++;
        table.assign(N, vector<int>(H));

        rep(i, 0, N) table[i][0] = arr[i];
        rep(j, 1, H) rep(i, 0, N){
            int right = i + (1 << (j-1));
            if(right < N) table[i][j] = min(table[i][j-1], table[right][j-1]);
            else table[i][j] = table[i][j-1];
        }
    }

    int query(int l, int r){ // [L, R]
        r++;
        int k = 31 - __builtin_clz(r-l);
        return min(table[l][k], table[r-(1 << k)][k]);
    }
};

void solve(){
    int N, M;
    N = getu<6, int>();
    M = getu<6, int>();
    vector<int> A(N);
    rep(i, 0, N) A[i] = getu<10, int>();
    RMQ rmq(N, A);
    while(M--){
        int l, r; l = getu<6, int>(); r = getu<6, int>();
        putu<10, int>(rmq.query(l-1, r-1));
    }
}