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); }
};