Disjoint Sparse Table
(ds/range_query/disjoint_sparse_table.hpp)

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

Overview

A Disjoint 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.

Unlike a normal Sparse Table, the monoid operation does not need to be idempotent. It can be used for operations like addition, multiplication, matrix multiplication, and other associative operations.

Template Parameters

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

Methods

Method	Description	Complexity
DisjointSparseTable()	Constructs an empty disjoint sparse table.	$O(1)$
DisjointSparseTable(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/disjoint_sparse_table.hpp"
#include "monoid/add.hpp"
#include <iostream>
#include <vector>

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

    m1une::ds::DisjointSparseTable<m1une::monoid::Add<long long>> dst(A);

    // Get sum of range [0, 3) -> 5 + 2 + 8 = 15
    std::cout << dst.prod(0, 3) << "\n";

    // Get sum of range [2, 5) -> 8 + 1 + 3 = 12
    std::cout << dst.prod(2, 5) << "\n";

    return 0;
}

Depends on

• Monoid Concept (monoid/concept.hpp)

Verified with

• verify/ds/range_query/disjoint_sparse_table.test.cpp

Code

#ifndef M1UNE_DISJOINT_SPARSE_TABLE_HPP
#define M1UNE_DISJOINT_SPARSE_TABLE_HPP 1

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

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

namespace m1une {
namespace ds {

// A Disjoint Sparse Table for static range queries.
// It supports any associative monoid, including non-idempotent and non-commutative ones.
template <m1une::monoid::IsMonoid Monoid>
struct DisjointSparseTable {
    using T = typename Monoid::value_type;

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

    void build() {
        if (_n == 0) return;

        for (int k = 0; k < int(_st.size()); k++) {
            int half = 1 << k;
            int block = half << 1;
            for (int start = 0; start < _n; start += block) {
                int mid = std::min(start + half, _n);
                int end = std::min(start + block, _n);

                _st[k][mid - 1] = _st[0][mid - 1];
                for (int i = mid - 2; i >= start; i--) {
                    _st[k][i] = Monoid::op(_st[0][i], _st[k][i + 1]);
                }

                if (mid == end) continue;
                _st[k][mid] = _st[0][mid];
                for (int i = mid + 1; i < end; i++) {
                    _st[k][i] = Monoid::op(_st[k][i - 1], _st[0][i]);
                }
            }
        }
    }

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

    // Constructs a disjoint sparse table from an existing vector in O(N log N) time.
    explicit DisjointSparseTable(const 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, Monoid::id()));
        for (int i = 0; i < _n; i++) {
            _st[0][i] = v[i];
        }
        build();
    }
    explicit DisjointSparseTable(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, Monoid::id()));
        for (int i = 0; i < _n; i++) {
            _st[0][i] = std::move(v[i]);
        }
        build();
    }

    // Constructs a disjoint 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 DisjointSparseTable(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, Monoid::id()));
        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]);
            }
        }
        build();
    }

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

        r--;
        if (l == r) return _st[0][l];

        int k = std::bit_width((unsigned int)(l ^ r)) - 1;
        return Monoid::op(_st[k][l], _st[k][r]);
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DISJOINT_SPARSE_TABLE_HPP

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



#include <algorithm>
#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 12 "ds/range_query/disjoint_sparse_table.hpp"

namespace m1une {
namespace ds {

// A Disjoint Sparse Table for static range queries.
// It supports any associative monoid, including non-idempotent and non-commutative ones.
template <m1une::monoid::IsMonoid Monoid>
struct DisjointSparseTable {
    using T = typename Monoid::value_type;

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

    void build() {
        if (_n == 0) return;

        for (int k = 0; k < int(_st.size()); k++) {
            int half = 1 << k;
            int block = half << 1;
            for (int start = 0; start < _n; start += block) {
                int mid = std::min(start + half, _n);
                int end = std::min(start + block, _n);

                _st[k][mid - 1] = _st[0][mid - 1];
                for (int i = mid - 2; i >= start; i--) {
                    _st[k][i] = Monoid::op(_st[0][i], _st[k][i + 1]);
                }

                if (mid == end) continue;
                _st[k][mid] = _st[0][mid];
                for (int i = mid + 1; i < end; i++) {
                    _st[k][i] = Monoid::op(_st[k][i - 1], _st[0][i]);
                }
            }
        }
    }

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

    // Constructs a disjoint sparse table from an existing vector in O(N log N) time.
    explicit DisjointSparseTable(const 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, Monoid::id()));
        for (int i = 0; i < _n; i++) {
            _st[0][i] = v[i];
        }
        build();
    }
    explicit DisjointSparseTable(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, Monoid::id()));
        for (int i = 0; i < _n; i++) {
            _st[0][i] = std::move(v[i]);
        }
        build();
    }

    // Constructs a disjoint 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 DisjointSparseTable(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, Monoid::id()));
        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]);
            }
        }
        build();
    }

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

        r--;
        if (l == r) return _st[0][l];

        int k = std::bit_width((unsigned int)(l ^ r)) - 1;
        return Monoid::op(_st[k][l], _st[k][r]);
    }
};

}  // namespace ds
}  // namespace m1une

Back to top page