Sparse Table
(ds/range_query/sparse_table.hpp)

• View this file on GitHub
• Last update: 2026-07-16 20:44:42+09:00
• Include: #include "ds/range_query/sparse_table.hpp"

Overview

A Sparse Table that answers static range queries in $O(1)$ time after an $O(N \log N)$ preprocessing step. It operates on any Monoid structure satisfying the m1une::monoid::IsMonoid concept.

[IMPORTANT] For $O(1)$ range queries to work correctly, the monoid operation MUST be idempotent. This means that Monoid::op(x, x) == x must hold for all valid values of x (e.g., Min, Max, GCD, Bitwise AND/OR). It cannot be used for operations like addition or multiplication.

Template Parameters

• Monoid: A struct representing the mathematical monoid, providing value_type, id(), and op(a, b). It must be an idempotent monoid.

Methods

Method	Description	Complexity
SparseTable()	Constructs an empty sparse table.	$O(1)$
SparseTable(const std::vector<T>& v)	Builds from v.	$O(N \log N)$
T prod(int l, int r)	Returns the monoid product over [l, r).	$O(1)$

Example

#include "ds/range_query/sparse_table.hpp"
#include "monoid/min.hpp"
#include <iostream>
#include <vector>

int main() {
    std::vector<long long> A = {5, 2, 8, 1, 3};

    // Initialize Sparse Table with Min Monoid
    m1une::ds::SparseTable<m1une::monoid::Min<long long>> st(A);

    // Get minimum of range [0, 3) -> min(5, 2, 8) = 2
    std::cout << st.prod(0, 3) << "\n";

    // Get minimum of range [2, 5) -> min(8, 1, 3) = 1
    std::cout << st.prod(2, 5) << "\n";

    return 0;
}

Depends on

• Monoid Concept (monoid/concept.hpp)

Required by

• Graph All (graph/all.hpp)
• Tree All (graph/tree/all.hpp)
• Sparse Table LCA (graph/tree/sparse_table_lca.hpp)
• Tree (graph/tree/tree.hpp)
• Virtual Tree (graph/tree/virtual_tree.hpp)

Verified with

• verify/ds/range_query/sparse_table.test.cpp
• verify/graph/cow_game.test.cpp
• verify/graph/graph_algorithms.test.cpp
• verify/graph/library_checker_lowest_common_ancestor.test.cpp
• verify/graph/range_edge_graph.test.cpp
• verify/graph/tree/tree_algorithms.test.cpp

Code

#ifndef M1UNE_SPARSE_TABLE_HPP
#define M1UNE_SPARSE_TABLE_HPP 1

#include <bit>
#include <cassert>
#include <concepts>
#include <utility>
#include <vector>

#include "../../monoid/concept.hpp"

namespace m1une {
namespace ds {

// A Sparse Table utilizing C++20 Concepts for type safety.
// It requires a Monoid struct that satisfies `m1une::monoid::IsMonoid`.
// [IMPORTANT] For O(1) range queries to work correctly, the monoid operation MUST be idempotent.
// i.e., Monoid::op(x, x) == x must hold (e.g., Min, Max, GCD, Bitwise AND/OR).
template <m1une::monoid::IsMonoid Monoid>
struct SparseTable {
    using T = typename Monoid::value_type;

   private:
    int _n;
    std::vector<std::vector<T>> _st;

   public:
    // Constructs an empty sparse table.
    SparseTable() : _n(0) {}

    // Constructs a sparse table from an existing vector in O(N log N) time.
    explicit SparseTable(const std::vector<T>& v) : _n(int(v.size())) {
        if (_n == 0) return;

        // Compute the maximum power of 2 needed
        int max_log = std::bit_width((unsigned int)_n);
        _st.assign(max_log, std::vector<T>(_n));

        // Initialize the base level
        for (int i = 0; i < _n; i++) {
            _st[0][i] = v[i];
        }

        // Build the sparse table
        for (int k = 1; k < max_log; k++) {
            for (int i = 0; i + (1 << k) <= _n; i++) {
                _st[k][i] = Monoid::op(_st[k - 1][i], _st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    explicit SparseTable(std::vector<T>&& v) : _n(int(v.size())) {
        if (_n == 0) return;

        int max_log = std::bit_width((unsigned int)_n);
        _st.assign(max_log, std::vector<T>(_n));

        for (int i = 0; i < _n; i++) {
            _st[0][i] = std::move(v[i]);
        }

        for (int k = 1; k < max_log; k++) {
            for (int i = 0; i + (1 << k) <= _n; i++) {
                _st[k][i] = Monoid::op(_st[k - 1][i], _st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    // Constructs a sparse table from a vector of a different type U.
    // It automatically adapts to the Monoid's initialization requirements:
    // 1. Monoid::make(val) if it exists.
    // 2. Monoid::make(val, index) if the monoid requires global indices.
    // 3. static_cast<T>(val) as a fallback for simple monoids.
    template <typename U>
    requires (!std::same_as<U, T>) && (
        requires(U x) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit SparseTable(const std::vector<U>& v) : _n(int(v.size())) {
        if (_n == 0) return;

        int max_log = std::bit_width((unsigned int)_n);
        _st.assign(max_log, std::vector<T>(_n));

        // Compile-time branching based on the available make() signature
        for (int i = 0; i < _n; i++) {
            if constexpr (requires(U x) { Monoid::make(x); }) {
                _st[0][i] = Monoid::make(v[i]);
            } else if constexpr (requires(U x, int idx) { Monoid::make(x, idx); }) {
                _st[0][i] = Monoid::make(v[i], i);
            } else {
                _st[0][i] = static_cast<T>(v[i]);
            }
        }
        for (int k = 1; k < max_log; k++) {
            for (int i = 0; i + (1 << k) <= _n; i++) {
                _st[k][i] = Monoid::op(_st[k - 1][i], _st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    // Returns the product (result of the monoid operation) in the range [l, r) in O(1) time.
    // Requires the monoid operation to be idempotent.
    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return Monoid::id();

        // Calculate the largest power of 2 less than or equal to the interval length
        int k = std::bit_width((unsigned int)(r - l)) - 1;
        return Monoid::op(_st[k][l], _st[k][r - (1 << k)]);
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_SPARSE_TABLE_HPP

#line 1 "ds/range_query/sparse_table.hpp"



#include <bit>
#include <cassert>
#include <concepts>
#include <utility>
#include <vector>

#line 1 "monoid/concept.hpp"



#line 5 "monoid/concept.hpp"

namespace m1une {
namespace monoid {

// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
    // 1. Must define `value_type`
    typename M::value_type;

    // 2. Must have a static method `id()` returning `value_type`
    { M::id() } -> std::same_as<typename M::value_type>;

    // 3. Must have a static method `op(a, b)` returning `value_type`
    { M::op(a, b) } -> std::same_as<typename M::value_type>;
};

// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
    { M::inv(a) } -> std::same_as<typename M::value_type>;
};

// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;

}  // namespace monoid
}  // namespace m1une


#line 11 "ds/range_query/sparse_table.hpp"

namespace m1une {
namespace ds {

// A Sparse Table utilizing C++20 Concepts for type safety.
// It requires a Monoid struct that satisfies `m1une::monoid::IsMonoid`.
// [IMPORTANT] For O(1) range queries to work correctly, the monoid operation MUST be idempotent.
// i.e., Monoid::op(x, x) == x must hold (e.g., Min, Max, GCD, Bitwise AND/OR).
template <m1une::monoid::IsMonoid Monoid>
struct SparseTable {
    using T = typename Monoid::value_type;

   private:
    int _n;
    std::vector<std::vector<T>> _st;

   public:
    // Constructs an empty sparse table.
    SparseTable() : _n(0) {}

    // Constructs a sparse table from an existing vector in O(N log N) time.
    explicit SparseTable(const std::vector<T>& v) : _n(int(v.size())) {
        if (_n == 0) return;

        // Compute the maximum power of 2 needed
        int max_log = std::bit_width((unsigned int)_n);
        _st.assign(max_log, std::vector<T>(_n));

        // Initialize the base level
        for (int i = 0; i < _n; i++) {
            _st[0][i] = v[i];
        }

        // Build the sparse table
        for (int k = 1; k < max_log; k++) {
            for (int i = 0; i + (1 << k) <= _n; i++) {
                _st[k][i] = Monoid::op(_st[k - 1][i], _st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    explicit SparseTable(std::vector<T>&& v) : _n(int(v.size())) {
        if (_n == 0) return;

        int max_log = std::bit_width((unsigned int)_n);
        _st.assign(max_log, std::vector<T>(_n));

        for (int i = 0; i < _n; i++) {
            _st[0][i] = std::move(v[i]);
        }

        for (int k = 1; k < max_log; k++) {
            for (int i = 0; i + (1 << k) <= _n; i++) {
                _st[k][i] = Monoid::op(_st[k - 1][i], _st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    // Constructs a sparse table from a vector of a different type U.
    // It automatically adapts to the Monoid's initialization requirements:
    // 1. Monoid::make(val) if it exists.
    // 2. Monoid::make(val, index) if the monoid requires global indices.
    // 3. static_cast<T>(val) as a fallback for simple monoids.
    template <typename U>
    requires (!std::same_as<U, T>) && (
        requires(U x) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit SparseTable(const std::vector<U>& v) : _n(int(v.size())) {
        if (_n == 0) return;

        int max_log = std::bit_width((unsigned int)_n);
        _st.assign(max_log, std::vector<T>(_n));

        // Compile-time branching based on the available make() signature
        for (int i = 0; i < _n; i++) {
            if constexpr (requires(U x) { Monoid::make(x); }) {
                _st[0][i] = Monoid::make(v[i]);
            } else if constexpr (requires(U x, int idx) { Monoid::make(x, idx); }) {
                _st[0][i] = Monoid::make(v[i], i);
            } else {
                _st[0][i] = static_cast<T>(v[i]);
            }
        }
        for (int k = 1; k < max_log; k++) {
            for (int i = 0; i + (1 << k) <= _n; i++) {
                _st[k][i] = Monoid::op(_st[k - 1][i], _st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    // Returns the product (result of the monoid operation) in the range [l, r) in O(1) time.
    // Requires the monoid operation to be idempotent.
    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return Monoid::id();

        // Calculate the largest power of 2 less than or equal to the interval length
        int k = std::bit_width((unsigned int)(r - l)) - 1;
        return Monoid::op(_st[k][l], _st[k][r - (1 << k)]);
    }
};

}  // namespace ds
}  // namespace m1une

Back to top page