RMQ - Sparse Table Algorithm

st.cc

#define MAXST   100000
#define LogMAXST    18

inline int clz(int x){return __builtin_clz(x);}
inline int lg2(int x){return !x ? -1 : 31 - clz(x);}

struct SparseTable {
    int N;
    int F[LogMAXST][MAXST];

    SparseTable() {}
    SparseTable(int n, int *A) {
        N = n;
        for (int i = 0; i < n; ++ i)
            F[0][i] = A[i];
        for (int k = 1; (1 << k) <= n; ++ k)
            for (int i = 0; i + (1 << k) - 1 < n; ++ i)
                F[k][i] = min(F[k - 1][i], F[k - 1][i + (1 << (k - 1))]);
    }

    // must be x <= y
    int Query(int x, int y) {
        if (x == y) return F[0][x];
        k = lg2(y - x + 1);
        return min(F[k][x], F[k][y - (1 << k) + 1]);
    }
};