Dynamic Dual Segment Tree
(ds/segtree/dynamic_dual_segtree.hpp)

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

Overview

m1une::ds::DynamicDualSegtree is a sparse dual segment tree for range monoid updates and point queries over a fixed integer coordinate domain. It is useful when the domain is large but range products are unnecessary.

apply(l, r, x) changes each point value v in [l, r) to Monoid::op(x, v). Composition order is preserved for non-commutative monoids. Nodes are stored in a contiguous pool and are allocated only for touched segments. Point queries are read-only and allocate nothing.

Template Parameters

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

Every untouched coordinate has the uniform initial_value. The default is Monoid::id().

Construction

DynamicDualSegtree(): creates an empty domain [0, 0).
DynamicDualSegtree(Index n): creates [0, n) with identity values.
DynamicDualSegtree(Index left, Index right): creates [left, right) with identity values.
DynamicDualSegtree(Index left, Index right, T initial_value): creates a domain with the specified uniform initial point value.

All constructors use $O(1)$ time and storage.

Methods

Let $U$ be the number of coordinates and $K$ the number of allocated nodes.

Method	Description	Complexity
`size_type size()`	Returns the unsigned domain length.	$O(1)$
`bool empty()`	Returns whether the coordinate domain is empty.	$O(1)$
`Index left_bound()`	Returns the left endpoint.	$O(1)$
`Index right_bound()`	Returns the right endpoint.	$O(1)$
`const T& initial_value()`	Returns the uniform initial point value.	$O(1)$
`void reserve(size_t n)`	Reserves space for `n` allocated nodes.	$O(K)$
`size_t node_count()`	Returns the number of allocated nodes.	$O(1)$
`void clear()`	Restores the initial state while retaining pool capacity.	$O(K)$
`void set(Index p, T x)`	Assigns `x` to coordinate `p` after earlier updates.	$O(\log U)$
`T get(Index p)`	Returns the current value at `p`.	$O(\log U)$
`T operator[](Index p)`	Equivalent to `get(p)`.	$O(\log U)$
`void apply(Index p, T x)`	Applies `x` to one coordinate.	$O(\log U)$
`void apply(Index l, Index r, T x)`	Applies `x` over `[l, r)`.	$O(\log U)$

After $Q$ updates, memory usage is $O(Q \log U)$ in the worst case.

Example

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

#include <iostream>

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

    Seg seg(-1'000'000'000LL, 1'000'000'001LL, 0);
    seg.apply(-100, 200, 7);
    seg.apply(50, 60, 3);

    std::cout << seg.get(0) << "\n";   // 7
    std::cout << seg.get(55) << "\n";  // 10
}

Depends on

Verified with

verify/ds/segtree/dynamic_dual_segtree.test.cpp

Code

#ifndef M1UNE_DYNAMIC_DUAL_SEGTREE_HPP
#define M1UNE_DYNAMIC_DUAL_SEGTREE_HPP 1

#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 dual segment tree over an integral half-open interval.
template <m1une::monoid::IsMonoid Monoid, std::integral Index = long long>
requires(!std::same_as<std::remove_cv_t<Index>, bool>)
struct DynamicDualSegtree {
    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;
        bool has_lazy;

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

    Index _left;
    Index _right;
    T _initial_value;
    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;
    }

    void all_apply(int& t, Index left, Index right, const T& x) {
        if (!t) t = new_node();
        Node& node = _nodes[t];
        if (std::midpoint(left, right) == left) {
            T value = node.has_lazy ? node.val : _initial_value;
            node.val = Monoid::op(x, value);
            node.has_lazy = true;
        } else {
            node.val = node.has_lazy ? Monoid::op(x, node.val) : x;
            node.has_lazy = true;
        }
    }

    void push(int t, Index left, Index right) {
        if (!_nodes[t].has_lazy) return;
        Index middle = std::midpoint(left, right);
        if (middle == left) return;

        T lazy = _nodes[t].val;
        int left_child = _nodes[t].left;
        int right_child = _nodes[t].right;
        all_apply(left_child, left, middle, lazy);
        all_apply(right_child, middle, right, lazy);

        Node& node = _nodes[t];
        node.left = left_child;
        node.right = right_child;
        node.val = Monoid::id();
        node.has_lazy = false;
    }

    int set_node(int t, Index left, Index right, Index p, T x) {
        if (!t) t = new_node();
        Index middle = std::midpoint(left, right);
        if (middle == left) {
            Node& node = _nodes[t];
            node.val = std::move(x);
            node.has_lazy = true;
            return t;
        }

        push(t, left, right);
        if (p < middle) {
            int child = set_node(_nodes[t].left, left, middle, p, std::move(x));
            _nodes[t].left = child;
        } else {
            int child = set_node(_nodes[t].right, middle, right, p, std::move(x));
            _nodes[t].right = child;
        }
        return t;
    }

    int apply_node(
        int t,
        Index left,
        Index right,
        Index query_left,
        Index query_right,
        const T& x
    ) {
        if (query_right <= left || right <= query_left) return t;
        if (query_left <= left && right <= query_right) {
            all_apply(t, left, right, x);
            return t;
        }

        if (!t) t = new_node();
        push(t, left, right);
        Index middle = std::midpoint(left, right);
        int left_child = apply_node(_nodes[t].left, left, middle, query_left, query_right, x);
        int right_child = apply_node(_nodes[t].right, middle, right, query_left, query_right, x);
        _nodes[t].left = left_child;
        _nodes[t].right = right_child;
        return t;
    }

    T compose(const T& inherited, int t) const {
        if (!t || !_nodes[t].has_lazy) return inherited;
        return Monoid::op(inherited, _nodes[t].val);
    }

   public:
    DynamicDualSegtree()
        : DynamicDualSegtree(Index(0), Index(0), Monoid::id()) {}

    explicit DynamicDualSegtree(Index n)
        : DynamicDualSegtree(Index(0), n, Monoid::id()) {
        if constexpr (std::signed_integral<Index>) assert(Index(0) <= n);
    }

    DynamicDualSegtree(Index left, Index right)
        : DynamicDualSegtree(left, right, Monoid::id()) {}

    DynamicDualSegtree(Index left, Index right, T initial_value)
        : _left(left),
          _right(right),
          _initial_value(std::move(initial_value)),
          _root(0),
          _nodes(1) {
        assert(left <= right);
    }

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

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

    Index left_bound() const {
        return _left;
    }

    Index right_bound() const {
        return _right;
    }

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

    void reserve(std::size_t node_capacity) {
        assert(node_capacity < std::numeric_limits<std::size_t>::max());
        _nodes.reserve(node_capacity + 1);
    }

    std::size_t node_count() const {
        return _nodes.size() - 1;
    }

    void clear() {
        _root = 0;
        _nodes.resize(1);
    }

    void set(Index p, T x) {
        assert(_left <= p && p < _right);
        _root = set_node(_root, _left, _right, p, std::move(x));
    }

    T get(Index p) const {
        assert(_left <= p && p < _right);
        int t = _root;
        Index left = _left;
        Index right = _right;
        T inherited = Monoid::id();

        while (t) {
            Index middle = std::midpoint(left, right);
            if (middle == left) {
                T value = _nodes[t].has_lazy ? _nodes[t].val : _initial_value;
                return Monoid::op(inherited, value);
            }
            inherited = compose(inherited, t);
            if (p < middle) {
                t = _nodes[t].left;
                right = middle;
            } else {
                t = _nodes[t].right;
                left = middle;
            }
        }
        return Monoid::op(inherited, _initial_value);
    }

    T operator[](Index p) const {
        return get(p);
    }

    void apply(Index p, const T& x) {
        assert(_left <= p && p < _right);
        apply(p, p + 1, x);
    }

    void apply(Index left, Index right, const T& x) {
        assert(_left <= left && left <= right && right <= _right);
        if (left == right) return;
        _root = apply_node(_root, _left, _right, left, right, x);
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DYNAMIC_DUAL_SEGTREE_HPP

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



#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 15 "ds/segtree/dynamic_dual_segtree.hpp"

namespace m1une {
namespace ds {

// A sparse dual segment tree over an integral half-open interval.
template <m1une::monoid::IsMonoid Monoid, std::integral Index = long long>
requires(!std::same_as<std::remove_cv_t<Index>, bool>)
struct DynamicDualSegtree {
    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;
        bool has_lazy;

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

    Index _left;
    Index _right;
    T _initial_value;
    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;
    }

    void all_apply(int& t, Index left, Index right, const T& x) {
        if (!t) t = new_node();
        Node& node = _nodes[t];
        if (std::midpoint(left, right) == left) {
            T value = node.has_lazy ? node.val : _initial_value;
            node.val = Monoid::op(x, value);
            node.has_lazy = true;
        } else {
            node.val = node.has_lazy ? Monoid::op(x, node.val) : x;
            node.has_lazy = true;
        }
    }

    void push(int t, Index left, Index right) {
        if (!_nodes[t].has_lazy) return;
        Index middle = std::midpoint(left, right);
        if (middle == left) return;

        T lazy = _nodes[t].val;
        int left_child = _nodes[t].left;
        int right_child = _nodes[t].right;
        all_apply(left_child, left, middle, lazy);
        all_apply(right_child, middle, right, lazy);

        Node& node = _nodes[t];
        node.left = left_child;
        node.right = right_child;
        node.val = Monoid::id();
        node.has_lazy = false;
    }

    int set_node(int t, Index left, Index right, Index p, T x) {
        if (!t) t = new_node();
        Index middle = std::midpoint(left, right);
        if (middle == left) {
            Node& node = _nodes[t];
            node.val = std::move(x);
            node.has_lazy = true;
            return t;
        }

        push(t, left, right);
        if (p < middle) {
            int child = set_node(_nodes[t].left, left, middle, p, std::move(x));
            _nodes[t].left = child;
        } else {
            int child = set_node(_nodes[t].right, middle, right, p, std::move(x));
            _nodes[t].right = child;
        }
        return t;
    }

    int apply_node(
        int t,
        Index left,
        Index right,
        Index query_left,
        Index query_right,
        const T& x
    ) {
        if (query_right <= left || right <= query_left) return t;
        if (query_left <= left && right <= query_right) {
            all_apply(t, left, right, x);
            return t;
        }

        if (!t) t = new_node();
        push(t, left, right);
        Index middle = std::midpoint(left, right);
        int left_child = apply_node(_nodes[t].left, left, middle, query_left, query_right, x);
        int right_child = apply_node(_nodes[t].right, middle, right, query_left, query_right, x);
        _nodes[t].left = left_child;
        _nodes[t].right = right_child;
        return t;
    }

    T compose(const T& inherited, int t) const {
        if (!t || !_nodes[t].has_lazy) return inherited;
        return Monoid::op(inherited, _nodes[t].val);
    }

   public:
    DynamicDualSegtree()
        : DynamicDualSegtree(Index(0), Index(0), Monoid::id()) {}

    explicit DynamicDualSegtree(Index n)
        : DynamicDualSegtree(Index(0), n, Monoid::id()) {
        if constexpr (std::signed_integral<Index>) assert(Index(0) <= n);
    }

    DynamicDualSegtree(Index left, Index right)
        : DynamicDualSegtree(left, right, Monoid::id()) {}

    DynamicDualSegtree(Index left, Index right, T initial_value)
        : _left(left),
          _right(right),
          _initial_value(std::move(initial_value)),
          _root(0),
          _nodes(1) {
        assert(left <= right);
    }

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

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

    Index left_bound() const {
        return _left;
    }

    Index right_bound() const {
        return _right;
    }

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

    void reserve(std::size_t node_capacity) {
        assert(node_capacity < std::numeric_limits<std::size_t>::max());
        _nodes.reserve(node_capacity + 1);
    }

    std::size_t node_count() const {
        return _nodes.size() - 1;
    }

    void clear() {
        _root = 0;
        _nodes.resize(1);
    }

    void set(Index p, T x) {
        assert(_left <= p && p < _right);
        _root = set_node(_root, _left, _right, p, std::move(x));
    }

    T get(Index p) const {
        assert(_left <= p && p < _right);
        int t = _root;
        Index left = _left;
        Index right = _right;
        T inherited = Monoid::id();

        while (t) {
            Index middle = std::midpoint(left, right);
            if (middle == left) {
                T value = _nodes[t].has_lazy ? _nodes[t].val : _initial_value;
                return Monoid::op(inherited, value);
            }
            inherited = compose(inherited, t);
            if (p < middle) {
                t = _nodes[t].left;
                right = middle;
            } else {
                t = _nodes[t].right;
                left = middle;
            }
        }
        return Monoid::op(inherited, _initial_value);
    }

    T operator[](Index p) const {
        return get(p);
    }

    void apply(Index p, const T& x) {
        assert(_left <= p && p < _right);
        apply(p, p + 1, x);
    }

    void apply(Index left, Index right, const T& x) {
        assert(_left <= left && left <= right && right <= _right);
        if (left == right) return;
        _root = apply_node(_root, _left, _right, left, right, x);
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

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

Dynamic Dual Segment Tree
(ds/segtree/dynamic_dual_segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Verified with

Code

Dynamic Dual Segment Tree (ds/segtree/dynamic_dual_segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Verified with

Code

Dynamic Dual Segment Tree
(ds/segtree/dynamic_dual_segtree.hpp)