AntInLoop

Sparse Table Data Structure Code Implementations

Production-ready Sparse Table Data Structure data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.

Study Sparse Table Data Structure Guide ยท Launch Visualizer

CPP Implementation

#include<bits/stdc++.h>
using namespace std;

// Segment Tree class
class SegmentTree {
private:
    vector<int> st, A; // st stores the segment tree, A is the input array
    int n;
    int left (int p) { return p << 1; } // left child index
    int right(int p) { return (p << 1) + 1; } // right child index

    void build(int p, int L, int R) { // build the segment tree
        if (L == R)
            st[p] = L;
        else {
            build(left(p), L , (L + R) / 2);
            build(right(p), (L + R) / 2 + 1, R );
            int p1 = st[left(p)], p2 = st[right(p)];
            st[p] = (A[p1] <= A[p2]) ? p1 : p2;
        }
    }

    int rmq(int p, int L, int R, int i, int j) { // range minimum query
        if (i > R || j < L) return -1;
        if (L >= i && R <= j) return st[p];

        int p1 = rmq(left(p) , L , (L+R) / 2, i, j);
        int p2 = rmq(right(p), (L+R) / 2 + 1, R , i, j);

        if (p1 == -1) return p2;
        if (p2 == -1) return p1;
        return (A[p1] <= A[p2]) ? p1 : p2;
    }

public:
    SegmentTree(const vector<int> &_A) {
        A = _A; n = (int)A.size();
        st.assign(4 * n, 0);
        build(1, 0, n - 1);
    }

    int rmq(int i, int j) { return rmq(1, 0, n - 1, i, j); }
};