Sparse Table을 지금 배웠으므로, 메모를 겸해 씁니다.

Sparse Table이란?

불변의 수열의 임의의 구간에 대한 최소치/최대치를, 전처리 $O(N\log N)$, 쿼리 마다 $O(1)$ 로 구하는 데이터 구조입니다.
숫자 열의 값이 변경될 수 있다면 SegmentTree를 사용합시다. SegmentTree 기사는 여기입니다.

메커니즘

모든 점을 시작점으로 하여 길이가 2인 구간의 최소값/최대값을 먼저 구해 둡니다. 이것은 $O(N\log N)$ 의 전 계산입니다.
쿼리에 대답할 때는 구간의 길이 이하에서 최대 2의 값을 취하고 구간의 앞쪽과 뒤쪽에 끼워 각각의 최소값을 구합니다.
이제 전체 구간을 덮을 수 있으며 최소값을 구할 수 있습니다.

테이블을 구축하면 이런 느낌이 듭니다.
구간의 길이로부터, 그 이하의 2 해야 할 것을 요구하는 것도 전 계산에 포함해 두면(자), 쿼리 마다 $O(1)$ 가 됩니다.

구현

template<typename T>
class SparseTable {
    T** table;
    int* logtable;
public:
    SparseTable(vector<T> vec) {
        int maxlength = 0;
        while ((1 << (maxlength + 1)) <= vec.size())maxlength++;
        table = new T * [maxlength + 1];
        logtable = new int[vec.size() + 1];
        rep(i, maxlength + 1) {
            table[i] = new T[vec.size()];
            rep(j, vec.size() - (1 << i) + 1) {
                if (i)table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
                else table[i][j] = vec[j];
            }
        }
        for (int i = 2; i <= vec.size(); i++) {
            logtable[i] = logtable[i >> 1] + 1;
        }
    }
    ~SparseTable() {
        rep(i, maxlength) delete[] table[i];
        delete[] table;
        delete[] logtable;
    }
    T query(int l, int r) {
        assert(l < r);
        int length = r - l;
        return min(table[logtable[length]][l], table[logtable[length]][r - (1 << logtable[length])]);
    }
};

꽤 복잡하고 가독성이 낮습니다. 죄송합니다.

결론

Segment Tree 쪽이 자신으로서는 쓰는 것이 편합니다만, Sparse Table는 정수배가 꽤 가볍습니다.
Sparse Table도 확실히 쓸 수 있도록 해 두면 좋을지도 모릅니다. (사용한 적은 없습니다)