Dynamic Segment Tree
(ds/segtree/dynamic_segtree.hpp)

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

Overview

m1une::ds::DynamicSegtree is a sparse segment tree for point assignments and monoid products over a large integer coordinate range. Unlike Segtree, it does not allocate storage for every coordinate. A node is created only when set first visits its segment, so a domain such as $[-10^{18}, 10^{18})$ is practical when only a small number of positions are updated.

The implementation uses one contiguous node pool rather than a separate heap allocation per node. Call reserve when the approximate number of nodes is known to avoid vector reallocations.

By default, unassigned coordinates have value Monoid::id(). A uniform arbitrary initial value can instead be supplied to the constructor. Products preserve coordinate order, so non-commutative monoids are supported.

Template Parameters

Monoid: A type satisfying m1une::monoid::IsMonoid.
Index: A non-bool integral coordinate type. The default is long long.

The monoid must provide:

using value_type = T
static T id()
static T op(const T& a, const T& b)

Construction

DynamicSegtree(): creates an empty tree over [0, 0).
DynamicSegtree(Index n): creates a tree over [0, n).
DynamicSegtree(Index left, Index right): creates a tree over [left, right).
DynamicSegtree(Index left, Index right, T initial_value): creates a tree over [left, right) with every coordinate initialized to initial_value.

The coordinate domain is fixed at construction. Construction caches untouched products for the possible segment lengths at each depth, using $O(\log U)$ memory and $O(\log^2 U)$ monoid operations. It does not create tree nodes.

Methods

Let $U$ be the number of integer coordinates in the domain.

Method	Description	Complexity
`size_type size()`	Returns the number of coordinates as the unsigned counterpart of `Index`.	$O(1)$
`bool empty()`	Returns whether the coordinate domain is empty.	$O(1)$
`Index left_bound()`	Returns the left endpoint of the domain.	$O(1)$
`Index right_bound()`	Returns the right endpoint of the domain.	$O(1)$
`const T& initial_value()`	Returns the value assigned to untouched coordinates.	$O(1)$
`void reserve(size_t n)`	Reserves storage for `n` allocated nodes, excluding the sentinel.	$O(K)$
`size_t node_count()`	Returns the number of nodes allocated by updates.	$O(1)$
`void clear()`	Restores every coordinate to the initial value and keeps pool capacity.	$O(K)$ to destroy stored node values
`void set(Index p, T x)`	Assigns `x` to coordinate `p`.	$O(\log U)$
`T get(Index p)`	Returns the value at `p`, or the initial value if `p` was never assigned.	$O(\log U)$
`T operator[](Index p)`	Equivalent to `get(p)`.	$O(\log U)$
`T prod(Index l, Index r)`	Returns the monoid product over `[l, r)`.	$O(\log U)$
`T all_prod()`	Returns the product over the entire domain.	$O(1)$
`Index max_right(Index l, F f)`	Returns the largest `r` for which `f(prod(l, r))` is true.	$O(\log U)$
`Index min_left(Index r, F f)`	Returns the smallest `l` for which `f(prod(l, r))` is true.	$O(\log U)$

Here $K$ is the number of allocated nodes. After $Q$ assignments, memory usage is $O(Q \log U)$ in the worst case. Updating an already allocated path does not create more nodes.

For max_right and min_left, f(Monoid::id()) must be true and f must be monotone along the searched products, as with the ordinary Segtree.

Example

#include "ds/segtree/dynamic_segtree.hpp"
#include "monoid/add.hpp"

#include <iostream>

int main() {
    using Sum = m1une::monoid::Add<long long>;
    using Seg = m1une::ds::DynamicSegtree<Sum>;

    Seg seg(-1'000'000'000LL, 1'000'000'001LL, 1);
    seg.reserve(256);

    seg.set(-500'000'000LL, 7);
    seg.set(900'000'000LL, 11);
    seg.set(-500'000'000LL, seg.get(-500'000'000LL) + 3);

    std::cout << seg.get(0) << "\n";                    // 1
    std::cout << seg.prod(-600'000'000LL, 0) << "\n";  // 600000009
}

Notes

set stores a monoid value directly. If the monoid has a make helper, call it before set.
Assigning the identity does not reclaim nodes. clear releases all logical assignments at once and reuses the pool capacity.
For versioned sparse point assignments and range products, use PersistentDynamicSegtree.
For sparse range updates and range products, use DynamicLazySegtree. Its constructor accepts a uniform initial leaf so size-aware actions can account for untouched coordinates.
For sparse range updates with point queries only, use DynamicDualSegtree.

Depends on

Verified with

verify/ds/segtree/dynamic_segtree.test.cpp

Code

#ifndef M1UNE_DYNAMIC_SEGTREE_HPP
#define M1UNE_DYNAMIC_SEGTREE_HPP 1

#include <array>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <limits>
#include <numeric>
#include <type_traits>
#include <utility>
#include <vector>

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

namespace m1une {
namespace ds {

// A sparse segment tree over an integral half-open interval.
// Nodes are allocated from a contiguous pool only when a position is touched.
template <m1une::monoid::IsMonoid Monoid, std::integral Index = long long>
requires(!std::same_as<std::remove_cv_t<Index>, bool>)
struct DynamicSegtree {
    using T = typename Monoid::value_type;
    using index_type = Index;
    using size_type = detail::dynamic_size_type<Index>;

   private:
    struct Node {
        T val;
        int left;
        int right;

        Node() : val(Monoid::id()), left(0), right(0) {}
    };

    static constexpr int path_capacity = std::numeric_limits<size_type>::digits + 1;

    detail::UniformMonoidDomain<Monoid, Index> _domain;
    int _root;
    std::vector<Node> _nodes;

    int new_node() {
        assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        _nodes.emplace_back();
        return int(_nodes.size()) - 1;
    }

    const T& value(int t, Index left, Index right, int depth) const {
        if (t) return _nodes[t].val;
        return _domain.default_product(depth, left, right);
    }

    void update(int t, Index left, Index right, int depth) {
        Index middle = std::midpoint(left, right);
        _nodes[t].val = Monoid::op(
            value(_nodes[t].left, left, middle, depth + 1),
            value(_nodes[t].right, middle, right, depth + 1)
        );
    }

    T prod_node(int t, Index l, Index r, int depth, Index ql, Index qr) const {
        if (qr <= l || r <= ql) return Monoid::id();
        if (ql <= l && r <= qr) return value(t, l, r, depth);
        Index m = std::midpoint(l, r);
        return Monoid::op(
            prod_node(t ? _nodes[t].left : 0, l, m, depth + 1, ql, qr),
            prod_node(t ? _nodes[t].right : 0, m, r, depth + 1, ql, qr)
        );
    }

    template <class F>
    Index max_right_node(
        int t,
        Index l,
        Index r,
        int depth,
        Index ql,
        T& sm,
        F& f
    ) const {
        if (r <= ql) return r;
        if (ql <= l) {
            T next = Monoid::op(sm, value(t, l, r, depth));
            if (f(next)) {
                sm = std::move(next);
                return r;
            }
            Index m = std::midpoint(l, r);
            if (m == l) return l;
        }
        Index m = std::midpoint(l, r);
        Index res = max_right_node(
            t ? _nodes[t].left : 0,
            l,
            m,
            depth + 1,
            ql,
            sm,
            f
        );
        if (res < m) return res;
        return max_right_node(
            t ? _nodes[t].right : 0,
            m,
            r,
            depth + 1,
            ql,
            sm,
            f
        );
    }

    template <class F>
    Index min_left_node(
        int t,
        Index l,
        Index r,
        int depth,
        Index qr,
        T& sm,
        F& f
    ) const {
        if (qr <= l) return l;
        if (r <= qr) {
            T next = Monoid::op(value(t, l, r, depth), sm);
            if (f(next)) {
                sm = std::move(next);
                return l;
            }
            Index m = std::midpoint(l, r);
            if (m == l) return r;
        }
        Index m = std::midpoint(l, r);
        Index res = min_left_node(
            t ? _nodes[t].right : 0,
            m,
            r,
            depth + 1,
            qr,
            sm,
            f
        );
        if (m < res) return res;
        return min_left_node(
            t ? _nodes[t].left : 0,
            l,
            m,
            depth + 1,
            qr,
            sm,
            f
        );
    }

   public:
    // Constructs an empty tree over [0, 0).
    DynamicSegtree() : DynamicSegtree(Index(0), Index(0)) {}

    // Constructs a tree over [0, n).
    explicit DynamicSegtree(Index n) : DynamicSegtree(Index(0), n) {
        if constexpr (std::signed_integral<Index>) assert(Index(0) <= n);
    }

    // Constructs a tree over [left, right).
    DynamicSegtree(Index left, Index right)
        : DynamicSegtree(left, right, Monoid::id()) {}

    // Constructs a tree over [left, right) with every coordinate initialized to
    // `initial_value`.
    DynamicSegtree(Index left, Index right, T initial_value)
        : _domain(left, right, std::move(initial_value)), _root(0), _nodes(1) {}

    // Returns the number of coordinates in the domain.
    size_type size() const {
        return _domain.size();
    }

    // Returns whether the coordinate domain is empty.
    bool empty() const {
        return _domain.empty();
    }

    // Returns the left endpoint of the coordinate domain.
    Index left_bound() const {
        return _domain.left_bound();
    }

    // Returns the right endpoint of the coordinate domain.
    Index right_bound() const {
        return _domain.right_bound();
    }

    // Returns the value assigned to untouched coordinates.
    const T& initial_value() const {
        return _domain.initial_value();
    }

    // Reserves space for `node_capacity` allocated nodes.
    void reserve(std::size_t node_capacity) {
        assert(node_capacity < std::numeric_limits<std::size_t>::max());
        _nodes.reserve(node_capacity + 1);
    }

    // Returns the number of allocated nodes, excluding the sentinel.
    std::size_t node_count() const {
        return _nodes.size() - 1;
    }

    // Restores every coordinate to the initial value while preserving capacity.
    void clear() {
        _root = 0;
        _nodes.resize(1);
    }

    // Sets the value at coordinate `p` to `x`.
    void set(Index p, T x) {
        assert(left_bound() <= p && p < right_bound());
        if (!_root) _root = new_node();

        std::array<int, path_capacity> path;
        std::array<Index, path_capacity> path_left;
        std::array<Index, path_capacity> path_right;
        int depth = 0;
        int t = _root;
        Index l = left_bound();
        Index r = right_bound();

        while (true) {
            assert(depth < path_capacity);
            path[depth] = t;
            path_left[depth] = l;
            path_right[depth] = r;
            depth++;
            Index m = std::midpoint(l, r);
            if (m == l) break;

            if (p < m) {
                int child = _nodes[t].left;
                if (!child) {
                    child = new_node();
                    _nodes[t].left = child;
                }
                t = child;
                r = m;
            } else {
                int child = _nodes[t].right;
                if (!child) {
                    child = new_node();
                    _nodes[t].right = child;
                }
                t = child;
                l = m;
            }
        }

        _nodes[t].val = std::move(x);
        for (int i = depth - 2; i >= 0; i--) {
            update(path[i], path_left[i], path_right[i], i);
        }
    }

    // Returns the value at coordinate `p`.
    T get(Index p) const {
        assert(left_bound() <= p && p < right_bound());
        int t = _root;
        Index l = left_bound();
        Index r = right_bound();
        int depth = 0;

        while (t) {
            Index m = std::midpoint(l, r);
            if (m == l) return value(t, l, r, depth);
            if (p < m) {
                t = _nodes[t].left;
                r = m;
            } else {
                t = _nodes[t].right;
                l = m;
            }
            depth++;
        }
        return initial_value();
    }

    // Returns the value at coordinate `p`.
    T operator[](Index p) const {
        return get(p);
    }

    // Returns the monoid product over [l, r).
    T prod(Index l, Index r) const {
        assert(left_bound() <= l && l <= r && r <= right_bound());
        if (l == r) return Monoid::id();
        return prod_node(_root, left_bound(), right_bound(), 0, l, r);
    }

    // Returns the monoid product over the entire coordinate domain.
    T all_prod() const {
        return value(_root, left_bound(), right_bound(), 0);
    }

    // Finds the largest r such that f(prod(l, r)) is true.
    template <class F>
    Index max_right(Index l, F f) const {
        assert(left_bound() <= l && l <= right_bound());
        assert(f(Monoid::id()));
        if (l == right_bound()) return right_bound();
        T sm = Monoid::id();
        return max_right_node(
            _root,
            left_bound(),
            right_bound(),
            0,
            l,
            sm,
            f
        );
    }

    // Finds the smallest l such that f(prod(l, r)) is true.
    template <class F>
    Index min_left(Index r, F f) const {
        assert(left_bound() <= r && r <= right_bound());
        assert(f(Monoid::id()));
        if (r == left_bound()) return left_bound();
        T sm = Monoid::id();
        return min_left_node(
            _root,
            left_bound(),
            right_bound(),
            0,
            r,
            sm,
            f
        );
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DYNAMIC_SEGTREE_HPP

#line 1 "ds/segtree/dynamic_segtree.hpp"



#include <array>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <limits>
#include <numeric>
#include <type_traits>
#include <utility>
#include <vector>

#line 1 "ds/segtree/dynamic_segtree_common.hpp"



#line 11 "ds/segtree/dynamic_segtree_common.hpp"

namespace m1une {
namespace ds {
namespace detail {

template <std::integral Index>
using dynamic_size_type = std::make_unsigned_t<Index>;

template <std::integral Index>
constexpr dynamic_size_type<Index> dynamic_distance(Index left, Index right) {
    return static_cast<dynamic_size_type<Index>>(right) - static_cast<dynamic_size_type<Index>>(left);
}

template <class Monoid, class Size>
typename Monoid::value_type monoid_repeat(typename Monoid::value_type value, Size count) {
    typename Monoid::value_type result = Monoid::id();
    while (count != 0) {
        if (count & 1) result = Monoid::op(result, value);
        count >>= 1;
        if (count != 0) value = Monoid::op(value, value);
    }
    return result;
}

template <class ActedMonoid>
typename ActedMonoid::value_type dynamic_mapping(
    const typename ActedMonoid::operator_type& f,
    const typename ActedMonoid::value_type& value
) {
    using F = typename ActedMonoid::operator_type;
    using T = typename ActedMonoid::value_type;
    if constexpr (requires(F g, T x, long long ord) { ActedMonoid::mapping(g, x, ord); }) {
        return ActedMonoid::mapping(f, value, 0);
    } else {
        return ActedMonoid::mapping(f, value);
    }
}

template <class ActedMonoid, class Size>
typename ActedMonoid::operator_type dynamic_shift(
    const typename ActedMonoid::operator_type& f,
    Size offset
) {
    using F = typename ActedMonoid::operator_type;
    if constexpr (requires(F g, long long ord) { ActedMonoid::op_shift(g, ord); }) {
        assert(offset <= static_cast<Size>(std::numeric_limits<long long>::max()));
        return ActedMonoid::op_shift(f, static_cast<long long>(offset));
    } else {
        return f;
    }
}

template <class Monoid, std::integral Index>
class UniformMonoidDomain {
   public:
    using T = typename Monoid::value_type;
    using size_type = dynamic_size_type<Index>;

   private:
    struct Level {
        size_type small_length;
        T small_value;
        T large_value;
    };

    Index _left;
    Index _right;
    T _initial_value;
    std::vector<Level> _levels;

   public:
    UniformMonoidDomain(Index left, Index right, T initial_value)
        : _left(left), _right(right), _initial_value(std::move(initial_value)) {
        assert(left <= right);
        size_type n = size();
        constexpr int digits = std::numeric_limits<size_type>::digits;
        _levels.reserve(digits + 1);
        for (int depth = 0; depth <= digits; depth++) {
            size_type small = depth == digits ? 0 : n >> depth;
            size_type large = small;
            if (depth != 0) {
                bool has_remainder;
                if (depth == digits) {
                    has_remainder = n != 0;
                } else {
                    size_type mask = (size_type(1) << depth) - 1;
                    has_remainder = (n & mask) != 0;
                }
                if (has_remainder) large++;
            }
            _levels.push_back(Level{
                small,
                monoid_repeat<Monoid>(_initial_value, small),
                monoid_repeat<Monoid>(_initial_value, large),
            });
        }
    }

    Index left_bound() const {
        return _left;
    }

    Index right_bound() const {
        return _right;
    }

    size_type size() const {
        return dynamic_distance(_left, _right);
    }

    bool empty() const {
        return _left == _right;
    }

    const T& initial_value() const {
        return _initial_value;
    }

    const T& default_product(int depth, Index left, Index right) const {
        assert(0 <= depth && depth < int(_levels.size()));
        const Level& level = _levels[depth];
        size_type length = dynamic_distance(left, right);
        if (length == level.small_length) return level.small_value;
        assert(length == level.small_length + 1);
        return level.large_value;
    }
};

}  // namespace detail
}  // namespace ds
}  // namespace m1une


#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 16 "ds/segtree/dynamic_segtree.hpp"

namespace m1une {
namespace ds {

// A sparse segment tree over an integral half-open interval.
// Nodes are allocated from a contiguous pool only when a position is touched.
template <m1une::monoid::IsMonoid Monoid, std::integral Index = long long>
requires(!std::same_as<std::remove_cv_t<Index>, bool>)
struct DynamicSegtree {
    using T = typename Monoid::value_type;
    using index_type = Index;
    using size_type = detail::dynamic_size_type<Index>;

   private:
    struct Node {
        T val;
        int left;
        int right;

        Node() : val(Monoid::id()), left(0), right(0) {}
    };

    static constexpr int path_capacity = std::numeric_limits<size_type>::digits + 1;

    detail::UniformMonoidDomain<Monoid, Index> _domain;
    int _root;
    std::vector<Node> _nodes;

    int new_node() {
        assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        _nodes.emplace_back();
        return int(_nodes.size()) - 1;
    }

    const T& value(int t, Index left, Index right, int depth) const {
        if (t) return _nodes[t].val;
        return _domain.default_product(depth, left, right);
    }

    void update(int t, Index left, Index right, int depth) {
        Index middle = std::midpoint(left, right);
        _nodes[t].val = Monoid::op(
            value(_nodes[t].left, left, middle, depth + 1),
            value(_nodes[t].right, middle, right, depth + 1)
        );
    }

    T prod_node(int t, Index l, Index r, int depth, Index ql, Index qr) const {
        if (qr <= l || r <= ql) return Monoid::id();
        if (ql <= l && r <= qr) return value(t, l, r, depth);
        Index m = std::midpoint(l, r);
        return Monoid::op(
            prod_node(t ? _nodes[t].left : 0, l, m, depth + 1, ql, qr),
            prod_node(t ? _nodes[t].right : 0, m, r, depth + 1, ql, qr)
        );
    }

    template <class F>
    Index max_right_node(
        int t,
        Index l,
        Index r,
        int depth,
        Index ql,
        T& sm,
        F& f
    ) const {
        if (r <= ql) return r;
        if (ql <= l) {
            T next = Monoid::op(sm, value(t, l, r, depth));
            if (f(next)) {
                sm = std::move(next);
                return r;
            }
            Index m = std::midpoint(l, r);
            if (m == l) return l;
        }
        Index m = std::midpoint(l, r);
        Index res = max_right_node(
            t ? _nodes[t].left : 0,
            l,
            m,
            depth + 1,
            ql,
            sm,
            f
        );
        if (res < m) return res;
        return max_right_node(
            t ? _nodes[t].right : 0,
            m,
            r,
            depth + 1,
            ql,
            sm,
            f
        );
    }

    template <class F>
    Index min_left_node(
        int t,
        Index l,
        Index r,
        int depth,
        Index qr,
        T& sm,
        F& f
    ) const {
        if (qr <= l) return l;
        if (r <= qr) {
            T next = Monoid::op(value(t, l, r, depth), sm);
            if (f(next)) {
                sm = std::move(next);
                return l;
            }
            Index m = std::midpoint(l, r);
            if (m == l) return r;
        }
        Index m = std::midpoint(l, r);
        Index res = min_left_node(
            t ? _nodes[t].right : 0,
            m,
            r,
            depth + 1,
            qr,
            sm,
            f
        );
        if (m < res) return res;
        return min_left_node(
            t ? _nodes[t].left : 0,
            l,
            m,
            depth + 1,
            qr,
            sm,
            f
        );
    }

   public:
    // Constructs an empty tree over [0, 0).
    DynamicSegtree() : DynamicSegtree(Index(0), Index(0)) {}

    // Constructs a tree over [0, n).
    explicit DynamicSegtree(Index n) : DynamicSegtree(Index(0), n) {
        if constexpr (std::signed_integral<Index>) assert(Index(0) <= n);
    }

    // Constructs a tree over [left, right).
    DynamicSegtree(Index left, Index right)
        : DynamicSegtree(left, right, Monoid::id()) {}

    // Constructs a tree over [left, right) with every coordinate initialized to
    // `initial_value`.
    DynamicSegtree(Index left, Index right, T initial_value)
        : _domain(left, right, std::move(initial_value)), _root(0), _nodes(1) {}

    // Returns the number of coordinates in the domain.
    size_type size() const {
        return _domain.size();
    }

    // Returns whether the coordinate domain is empty.
    bool empty() const {
        return _domain.empty();
    }

    // Returns the left endpoint of the coordinate domain.
    Index left_bound() const {
        return _domain.left_bound();
    }

    // Returns the right endpoint of the coordinate domain.
    Index right_bound() const {
        return _domain.right_bound();
    }

    // Returns the value assigned to untouched coordinates.
    const T& initial_value() const {
        return _domain.initial_value();
    }

    // Reserves space for `node_capacity` allocated nodes.
    void reserve(std::size_t node_capacity) {
        assert(node_capacity < std::numeric_limits<std::size_t>::max());
        _nodes.reserve(node_capacity + 1);
    }

    // Returns the number of allocated nodes, excluding the sentinel.
    std::size_t node_count() const {
        return _nodes.size() - 1;
    }

    // Restores every coordinate to the initial value while preserving capacity.
    void clear() {
        _root = 0;
        _nodes.resize(1);
    }

    // Sets the value at coordinate `p` to `x`.
    void set(Index p, T x) {
        assert(left_bound() <= p && p < right_bound());
        if (!_root) _root = new_node();

        std::array<int, path_capacity> path;
        std::array<Index, path_capacity> path_left;
        std::array<Index, path_capacity> path_right;
        int depth = 0;
        int t = _root;
        Index l = left_bound();
        Index r = right_bound();

        while (true) {
            assert(depth < path_capacity);
            path[depth] = t;
            path_left[depth] = l;
            path_right[depth] = r;
            depth++;
            Index m = std::midpoint(l, r);
            if (m == l) break;

            if (p < m) {
                int child = _nodes[t].left;
                if (!child) {
                    child = new_node();
                    _nodes[t].left = child;
                }
                t = child;
                r = m;
            } else {
                int child = _nodes[t].right;
                if (!child) {
                    child = new_node();
                    _nodes[t].right = child;
                }
                t = child;
                l = m;
            }
        }

        _nodes[t].val = std::move(x);
        for (int i = depth - 2; i >= 0; i--) {
            update(path[i], path_left[i], path_right[i], i);
        }
    }

    // Returns the value at coordinate `p`.
    T get(Index p) const {
        assert(left_bound() <= p && p < right_bound());
        int t = _root;
        Index l = left_bound();
        Index r = right_bound();
        int depth = 0;

        while (t) {
            Index m = std::midpoint(l, r);
            if (m == l) return value(t, l, r, depth);
            if (p < m) {
                t = _nodes[t].left;
                r = m;
            } else {
                t = _nodes[t].right;
                l = m;
            }
            depth++;
        }
        return initial_value();
    }

    // Returns the value at coordinate `p`.
    T operator[](Index p) const {
        return get(p);
    }

    // Returns the monoid product over [l, r).
    T prod(Index l, Index r) const {
        assert(left_bound() <= l && l <= r && r <= right_bound());
        if (l == r) return Monoid::id();
        return prod_node(_root, left_bound(), right_bound(), 0, l, r);
    }

    // Returns the monoid product over the entire coordinate domain.
    T all_prod() const {
        return value(_root, left_bound(), right_bound(), 0);
    }

    // Finds the largest r such that f(prod(l, r)) is true.
    template <class F>
    Index max_right(Index l, F f) const {
        assert(left_bound() <= l && l <= right_bound());
        assert(f(Monoid::id()));
        if (l == right_bound()) return right_bound();
        T sm = Monoid::id();
        return max_right_node(
            _root,
            left_bound(),
            right_bound(),
            0,
            l,
            sm,
            f
        );
    }

    // Finds the smallest l such that f(prod(l, r)) is true.
    template <class F>
    Index min_left(Index r, F f) const {
        assert(left_bound() <= r && r <= right_bound());
        assert(f(Monoid::id()));
        if (r == left_bound()) return left_bound();
        T sm = Monoid::id();
        return min_left_node(
            _root,
            left_bound(),
            right_bound(),
            0,
            r,
            sm,
            f
        );
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Dynamic Segment Tree
(ds/segtree/dynamic_segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Notes

Depends on

Verified with

Code

Dynamic Segment Tree (ds/segtree/dynamic_segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Notes

Depends on

Verified with

Code

Dynamic Segment Tree
(ds/segtree/dynamic_segtree.hpp)