Sparse Table

Static range query structure — O(1) for idempotent operations (min/max/gcd), O(log n) for non-idempotent.

[Data Structures]|

Jul 9, 2026

|explanatory_notes.md|

#sparse-table#rmq#range-minimum#static

$cat source_code/

cpp

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

using ll = long long;
#define sz(x) int(x.size())

template <typename T>
struct MinOp {
  constexpr T operator()(const T& a, const T& b) const { return a < b ? a : b; }
};

template <typename T = int, typename Op = MinOp<T>, int Base = 0, typename numsType = T>
class Sparse_Table {
 private:
  int n, LOG;
  vector<vector<T>> table;
  vector<int> Bin_Log;
  Op operation;
  T DEFAULT;

  void Build_Table() {
    for (int log = 1; log < LOG; log++)
      for (int i = 1; i + (1 << log) - 1 <= n; i++)
        table[i][log] =
            operation(table[i][log - 1], table[i + (1 << (log - 1))][log - 1]);
  }

  T query_1(int L, int R) {
    int log = Bin_Log[R - L + 1];
    return operation(table[L][log], table[R - (1 << log) + 1][log]);
  }

  T query_log_n(int L, int R) {
    T answer = DEFAULT;
    for (int log = LOG; log >= 0; log--) {
      if (L + (1 << log) - 1 <= R) {
        answer = operation(answer, table[L][log]);
        L += 1 << log;
      }
    }
    return answer;
  }

 public:
  Sparse_Table(int N = 0, const vector<numsType>& vec = vector<numsType>(),
               Op op = Op{}, T def = numeric_limits<T>::max()) : n(N), LOG(__lg(n) + 1), operation(op), DEFAULT(def) {
    table = vector<vector<T>>(n + 10, vector<T>(LOG, DEFAULT));
    Bin_Log = vector<int>(n + 10);
    for (int i = 2; i <= n; i++) Bin_Log[i] = Bin_Log[i >> 1] + 1;
    for (int i = 1; i <= N; i++) table[i][0] = T(vec[i - !Base]);
    Build_Table();
  }

  T query(int L, int R, bool is_overlap = false) {
    return !is_overlap ? query_1(L, R) : query_log_n(L, R);
  }
};

void Solve() {
  // write your code here
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) Solve();
  return 0;
}

69 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Sparse Table — Static RMQ / Range Query

Quick Start (ECPC)

Range min, 0-indexed:

void Solve()
{
    int n; cin >> n;
    vector arr(n);
    for (auto &x : arr) cin >> x;
    Sparse_Table st(n, arr);    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;
        cout << st.query(l, r) << "\n";  // O(1) min
    }
}

Template Params

T — answer/value type (default int)

Op — binary combine functor (default MinOp)

Base — 0 = 0-indexed, 1 = 1-indexed

numsType — input array type (default T)

Constructor

Sparse_Table st(n, vec, op, def);
// n   — array size
// vec — input array
// op  — combine function (default: min)
// def — identity element (default: numeric_limits::max())

Methods

query(L, R) — O(1) range query (idempotent ops: min, max, gcd)

query(L, R, true) — O(log n) range query (all ops: sum, etc.)

Common Customizations

Range min (default):

Sparse_Table st(n, arr);
cout << st.query(l, r);  // O(1)

Range max:

struct MaxOp { int operator()(int a, int b) const { return max(a, b); } };
Sparse_Table st(n, arr);
cout << st.query(l, r);  // O(1)

Range sum (O(log n) queries):

auto sumOp = [](ll a, ll b){ return a + b; };
Sparse_Table st(n, arr, sumOp, 0LL);
cout << st.query(l, r, true);  // must pass true

Notes

is_overlap = false (default): O(1), only for idempotent ops (min, max, gcd).

is_overlap = true: O(log n), correct for all ops including sum.

1-indexed: use Base = 1 template param.