Sparse Table

Sparse Table สำหรับ Static Range Minimum/Maximum Queries

Sparse Table

Sparse Table เป็นโครงสร้างข้อมูลสำหรับ Range Minimum Query (RMQ) และ operations ที่เป็น idempotent ( $f(a, a) = a$ ) บน static arrays

คุณสมบัติ

Build: $O(n \log n)$
Query: $O(1)$
No updates - static data structure

แนวคิด

Precompute คำตอบสำหรับทุก range ที่มีความยาวเป็น power of 2:

$st[i][j] = \min(arr[i], arr[i+1], \ldots, arr[i + 2^j - 1])$

Implementation

Basic Sparse Table (Min/Max)

class SparseTable {
    vector<vector<int>> st;
    vector<int> log;
    int n, LOG;
    
    int combine(int a, int b) {
        return min(a, b);  // หรือ max(a, b)
    }
    
public:
    SparseTable(vector<int>& arr) {
        n = arr.size();
        LOG = 32 - __builtin_clz(n);
        
        // Precompute logs
        log.resize(n + 1);
        log[1] = 0;
        for (int i = 2; i <= n; i++) {
            log[i] = log[i / 2] + 1;
        }
        
        // Build sparse table
        st.assign(n, vector<int>(LOG));
        
        // Base case: length 1
        for (int i = 0; i < n; i++) {
            st[i][0] = arr[i];
        }
        
        // Fill for longer ranges
        for (int j = 1; j < LOG; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = combine(st[i][j-1], st[i + (1 << (j-1))][j-1]);
            }
        }
    }
    
    // Query [l, r] (0-indexed, inclusive)
    int query(int l, int r) {
        int len = r - l + 1;
        int k = log[len];
        return combine(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

Sparse Table for GCD

GCD เป็น idempotent: $\gcd(a, a) = a$

class SparseTableGCD {
    vector<vector<long long>> st;
    vector<int> log;
    int n, LOG;
    
public:
    SparseTableGCD(vector<long long>& arr) {
        n = arr.size();
        LOG = 32 - __builtin_clz(n);
        log.resize(n + 1);
        log[1] = 0;
        for (int i = 2; i <= n; i++) log[i] = log[i/2] + 1;
        
        st.assign(n, vector<long long>(LOG));
        for (int i = 0; i < n; i++) st[i][0] = arr[i];
        
        for (int j = 1; j < LOG; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = __gcd(st[i][j-1], st[i + (1 << (j-1))][j-1]);
            }
        }
    }
    
    long long query(int l, int r) {
        int k = log[r - l + 1];
        return __gcd(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

Sparse Table for Sum (Non-idempotent)

สำหรับ operations ที่ไม่ idempotent ต้องแบ่ง range ไม่ให้ overlap:

class SparseTableSum {
    vector<vector<long long>> st;
    vector<int> log;
    int n, LOG;
    
public:
    SparseTableSum(vector<long long>& arr) {
        n = arr.size();
        LOG = 32 - __builtin_clz(n);
        log.resize(n + 1);
        log[1] = 0;
        for (int i = 2; i <= n; i++) log[i] = log[i/2] + 1;
        
        st.assign(n, vector<long long>(LOG));
        for (int i = 0; i < n; i++) st[i][0] = arr[i];
        
        for (int j = 1; j < LOG; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = st[i][j-1] + st[i + (1 << (j-1))][j-1];
            }
        }
    }
    
    // O(log n) query
    long long query(int l, int r) {
        long long sum = 0;
        for (int j = LOG - 1; j >= 0; j--) {
            if ((1 << j) <= r - l + 1) {
                sum += st[l][j];
                l += (1 << j);
            }
        }
        return sum;
    }
};

2D Sparse Table

สำหรับ 2D RMQ:

class SparseTable2D {
    vector<vector<vector<vector<int>>>> st;
    vector<int> log;
    int n, m, LOG;
    
public:
    SparseTable2D(vector<vector<int>>& arr) {
        n = arr.size();
        m = arr[0].size();
        LOG = max(32 - __builtin_clz(n), 32 - __builtin_clz(m));
        
        log.resize(max(n, m) + 1);
        log[1] = 0;
        for (int i = 2; i <= max(n, m); i++) log[i] = log[i/2] + 1;
        
        st.assign(n, vector<vector<vector<int>>>(m, 
            vector<vector<int>>(LOG, vector<int>(LOG))));
        
        // Build
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                st[i][j][0][0] = arr[i][j];
            }
        }
        
        // First dimension
        for (int jj = 0; jj < LOG; jj++) {
            for (int ii = 1; ii < LOG; ii++) {
                for (int i = 0; i + (1 << ii) <= n; i++) {
                    for (int j = 0; j + (1 << jj) <= m; j++) {
                        st[i][j][ii][jj] = min(
                            st[i][j][ii-1][jj],
                            st[i + (1 << (ii-1))][j][ii-1][jj]
                        );
                    }
                }
            }
        }
        
        // Second dimension
        for (int ii = 0; ii < LOG; ii++) {
            for (int jj = 1; jj < LOG; jj++) {
                for (int i = 0; i + (1 << ii) <= n; i++) {
                    for (int j = 0; j + (1 << jj) <= m; j++) {
                        st[i][j][ii][jj] = min(
                            st[i][j][ii][jj-1],
                            st[i][j + (1 << (jj-1))][ii][jj-1]
                        );
                    }
                }
            }
        }
    }
    
    // Query rectangle [r1, c1] to [r2, c2]
    int query(int r1, int c1, int r2, int c2) {
        int ki = log[r2 - r1 + 1];
        int kj = log[c2 - c1 + 1];
        
        return min({
            st[r1][c1][ki][kj],
            st[r2 - (1 << ki) + 1][c1][ki][kj],
            st[r1][c2 - (1 << kj) + 1][ki][kj],
            st[r2 - (1 << ki) + 1][c2 - (1 << kj) + 1][ki][kj]
        });
    }
};

Applications

1. Range Minimum Query

SparseTable st(arr);
int minVal = st.query(l, r);

2. LCA with Euler Tour

// Build Euler tour, then use RMQ on depths
class LCA_ST {
    SparseTable st;
    vector<int> first, euler, depth;
    // ...
};

3. Range GCD

SparseTableGCD st(arr);
long long g = st.query(l, r);

4. Next Greater Element (Range)

หา element ที่มากกว่า $x$ ตัวแรกใน range

Sparse Table vs Segment Tree

Aspect	Sparse Table	Segment Tree
Build	$O(n \log n)$	$O(n)$
Query	$O(1)$	$O(\log n)$
Update	ไม่รองรับ	$O(\log n)$
Space	$O(n \log n)$	$O(n)$
Operations	Idempotent	Any associative

Complexity

Operation	Time	Space
Build	$O(n \log n)$	$O(n \log n)$
Query (idempotent)	$O(1)$	-
Query (non-idempotent)	$O(\log n)$	-
2D Build	$O(nm \log n \log m)$	$O(nm \log n \log m)$
2D Query	$O(1)$	-

Tips

Idempotent operations only สำหรับ $O(1)$ query: min, max, gcd, OR, AND
Precompute logs เพื่อหลีกเลี่ยง log2() ที่ช้า
Static data - ถ้าต้องการ updates ใช้ Segment Tree แทน
Memory - ใช้ memory $O(n \log n)$ ซึ่งอาจมากสำหรับ $n$ ใหญ่