스파스 테이블과 RMQ (Range Minimum Query)

스파스 테이블이란

스파스 테이블은 **멱등 연산(최솟값, 최댓값, GCD)**의 구간 쿼리를 O(1)에 처리하는 자료구조입니다. 전처리 O(N log N), 쿼리 O(1)로 오프라인 정적 배열에 최적입니다.

멱등 조건: f(f(a, b), b) = f(a, b) — 겹치는 구간에 적용해도 결과가 동일.

구축 (O(N log N))

class SparseTable {
    vector<vector<int>> table;
    vector<int>         log2_;
    int n;

public:
    SparseTable(const vector<int>& arr) : n(arr.size()),
            table(arr.size(), vector<int>(__lg(arr.size()) + 1)),
            log2_(arr.size() + 1) {
        // log2 사전 계산
        log2_[1] = 0;
        for (int i = 2; i <= n; i++)
            log2_[i] = log2_[i / 2] + 1;

        // 초기화: 길이 1 구간
        for (int i = 0; i < n; i++)
            table[i][0] = arr[i];

        // DP: table[i][j] = arr[i..i+2^j-1] 최솟값
        for (int j = 1; (1 << j) <= n; j++)
            for (int i = 0; i + (1 << j) <= n; i++)
                table[i][j] = min(table[i][j - 1],
                                  table[i + (1 << (j - 1))][j - 1]);
    }

    // [l, r] 최솟값 O(1)
    int query(int l, int r) {
        int k = log2_[r - l + 1];
        return min(table[l][k], table[r - (1 << k) + 1][k]);
    }
};

사용 예시

vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
SparseTable st(arr);

cout << st.query(2, 7);  // 1 (arr[3] = 1)
cout << st.query(0, 9);  // 1 (전체 최솟값)
cout << st.query(5, 8);  // 2 (arr[6] = 2)

GCD 스파스 테이블

GCD도 멱등 연산입니다.

class GCDSparseTable {
    vector<vector<int>> table;
    int n;
    vector<int> log2_;

public:
    GCDSparseTable(const vector<int>& arr) : n(arr.size()),
            table(arr.size(), vector<int>(__lg(arr.size()) + 1)),
            log2_(arr.size() + 1) {
        log2_[1] = 0;
        for (int i = 2; i <= n; i++) log2_[i] = log2_[i/2] + 1;
        for (int i = 0; i < n; i++) table[i][0] = arr[i];
        for (int j = 1; (1<<j) <= n; j++)
            for (int i = 0; i+(1<<j) <= n; i++)
                table[i][j] = __gcd(table[i][j-1], table[i+(1<<(j-1))][j-1]);
    }

    int query(int l, int r) {
        int k = log2_[r - l + 1];
        return __gcd(table[l][k], table[r-(1<<k)+1][k]);
    }
};

LCA에서의 활용 (Euler Tour + RMQ)

트리의 LCA(최소 공통 조상)를 O(N log N) 전처리 + O(1) 쿼리로 구합니다.

// 오일러 투어로 LCA → RMQ 변환
struct LCA {
    vector<int> euler, depth, first;
    SparseTable st;

    LCA(int root, const vector<vector<int>>& adj) :
            euler(2 * adj.size() - 1),
            depth(2 * adj.size() - 1),
            first(adj.size()),
            st({}) {

        int idx = 0;
        function<void(int, int, int)> dfs = [&](int v, int p, int d) {
            first[v] = idx;
            euler[idx] = v; depth[idx++] = d;
            for (int u : adj[v]) {
                if (u == p) continue;
                dfs(u, v, d + 1);
                euler[idx] = v; depth[idx++] = d;
            }
        };
        dfs(root, -1, 0);
        st = SparseTable(depth);
    }

    int query(int u, int v) {
        int l = first[u], r = first[v];
        if (l > r) swap(l, r);
        int idx = st.queryIndex(l, r);  // 최솟값 인덱스 반환 버전
        return euler[idx];
    }
};

세그먼트 트리 vs 스파스 테이블

항목	스파스 테이블	세그먼트 트리
전처리	O(N log N)	O(N)
쿼리	O(1)	O(log N)
업데이트	❌ 불가	✅ O(log N)
지원 연산	멱등 연산만	임의
메모리	O(N log N)	O(N)

정리

• 정적 배열의 최솟값/최댓값/GCD 쿼리에 최적 (수정 없음)
• 전처리 O(N log N), 쿼리 O(1) — 대량 쿼리 처리에 유리
• Euler Tour와 결합하면 LCA를 O(1)에 처리 가능
• 배열이 자주 변경된다면 세그먼트 트리 사용