Dual Segment Tree
(ds/segtree/dual_segtree.hpp)

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

Overview

m1une::ds::DualSegtree is a generic dual segment tree for range updates and point queries. Both updates and stored point values are elements of the same monoid.

Use it when you only need point queries after range updates. If you also need range queries, use LazySegtree instead.

Template Parameters

Monoid: A type satisfying m1une::monoid::IsMonoid.

The monoid must provide:

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

apply(l, r, x) updates each point value v in [l, r) to Monoid::op(x, v).

Construction

DualSegtree(): creates an empty tree.
DualSegtree(int n): creates n elements initialized with Monoid::id().
DualSegtree(const std::vector<T>& v): builds from monoid values.
DualSegtree(std::vector<T>&& v): builds from moved monoid values.
DualSegtree(const std::vector<U>& v): builds from another value type when Monoid::make(value), Monoid::make(value, index), or static_cast<T>(value) is available.

Construction takes $O(N)$ time.

Methods

Method	Description	Complexity
`int size()`	Returns the number of elements.	$O(1)$
`bool empty()`	Returns whether the tree has no elements.	$O(1)$
`void set(int p, T x)`	Pushes pending updates on the path and assigns `x` to index `p`.	$O(\log N)$
`T get(int p)`	Pushes pending updates on the path and returns the value at index `p`.	$O(\log N)$
`T operator[](int p)`	Returns the value at index `p`.	$O(\log N)$
`void apply(int p, T x)`	Applies `x` to index `p`.	$O(\log N)$
`void apply(int l, int r, T x)`	Applies `x` to every element in `[l, r)`.	$O(\log N)$
`std::vector<T> to_vector()`	Pushes all pending updates and returns all elements.	$O(N)$
`std::vector<T> to_vector(int l, int r)`	Returns the elements in `[l, r)`.	$O((r - l) \log N)$

Example

#include "ds/segtree/dual_segtree.hpp"
#include "monoid/add.hpp"
#include <iostream>
#include <vector>

int main() {
    using Add = m1une::monoid::Add<long long>;
    m1une::ds::DualSegtree<Add> seg(std::vector<long long>{1, 2, 3, 4});

    seg.apply(1, 4, 10);

    std::cout << seg.get(0) << "\n";  // 1
    std::cout << seg.get(2) << "\n";  // 13

    return 0;
}

Depends on

Verified with

verify/ds/segtree/dual_segtree.test.cpp

Code

#ifndef M1UNE_DUAL_SEGTREE_HPP
#define M1UNE_DUAL_SEGTREE_HPP 1

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

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

namespace m1une {
namespace ds {

// A generic Dual Segment Tree for range monoid updates and point queries.
template <m1une::monoid::IsMonoid Monoid>
struct DualSegtree {
    using T = typename Monoid::value_type;

   private:
    int _n, _size, _log;
    std::vector<T> _d;

    void all_apply(int k, const T& x) {
        _d[k] = Monoid::op(x, _d[k]);
    }

    void push(int k) {
        all_apply(2 * k, _d[k]);
        all_apply(2 * k + 1, _d[k]);
        _d[k] = Monoid::id();
    }

   public:
    // Constructs an empty dual segment tree.
    DualSegtree() : DualSegtree(0) {}

    // Constructs a dual segment tree of size `n`, initialized with the identity element.
    explicit DualSegtree(int n) : DualSegtree(std::vector<T>(n, Monoid::id())) {}

    // Constructs a dual segment tree from an existing vector.
    explicit DualSegtree(const std::vector<T>& v) : _n(int(v.size())) {
        _size = m1une::math::bit_ceil((unsigned int)(_n));
        _log = 0;
        while ((1U << _log) < (unsigned int)(_size)) _log++;
        _d.assign(2 * _size, Monoid::id());
        for (int i = 0; i < _n; i++) _d[_size + i] = v[i];
    }
    explicit DualSegtree(std::vector<T>&& v) : _n(int(v.size())) {
        _size = m1une::math::bit_ceil((unsigned int)(_n));
        _log = 0;
        while ((1U << _log) < (unsigned int)(_size)) _log++;
        _d.assign(2 * _size, Monoid::id());
        for (int i = 0; i < _n; i++) _d[_size + i] = std::move(v[i]);
    }

    // Constructs a dual segment tree 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 DualSegtree(const std::vector<U>& v) : _n(int(v.size())) {
        _size = m1une::math::bit_ceil((unsigned int)(_n));
        _log = 0;
        while ((1U << _log) < (unsigned int)(_size)) _log++;
        _d.assign(2 * _size, Monoid::id());
        for (int i = 0; i < _n; i++) {
            if constexpr (requires(U x) { Monoid::make(x); }) {
                _d[_size + i] = Monoid::make(v[i]);
            } else if constexpr (requires(U x, int idx) { Monoid::make(x, idx); }) {
                _d[_size + i] = Monoid::make(v[i], i);
            } else {
                _d[_size + i] = static_cast<T>(v[i]);
            }
        }
    }

    // Returns the number of elements.
    int size() const {
        return _n;
    }

    // Returns whether the tree is empty.
    bool empty() const {
        return _n == 0;
    }

    // Assigns x to the p-th element after applying pending updates on its path.
    void set(int p, T x) {
        assert(0 <= p && p < _n);
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        _d[p] = std::move(x);
    }

    // Returns the value of the p-th element after applying pending updates on its path.
    T get(int p) {
        assert(0 <= p && p < _n);
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        return _d[p];
    }

    // Returns the value of the p-th element.
    T operator[](int p) {
        return get(p);
    }

    // Applies x to the p-th element.
    void apply(int p, T x) {
        assert(0 <= p && p < _n);
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        all_apply(p, x);
    }

    // Applies x to all elements in the range [l, r).
    void apply(int l, int r, T x) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += _size;
        r += _size;

        for (int i = _log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        while (l < r) {
            if (l & 1) all_apply(l++, x);
            if (r & 1) all_apply(--r, x);
            l >>= 1;
            r >>= 1;
        }
    }

    // Returns all elements as a vector after applying all pending updates.
    std::vector<T> to_vector() {
        for (int k = 1; k < _size; k++) push(k);
        std::vector<T> res;
        res.reserve(_n);
        for (int i = 0; i < _n; i++) res.push_back(_d[_size + i]);
        return res;
    }

    // Returns the elements in the range [l, r) as a vector.
    std::vector<T> to_vector(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        std::vector<T> res;
        res.reserve(r - l);
        for (int i = l; i < r; i++) res.push_back(get(i));
        return res;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DUAL_SEGTREE_HPP

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



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

#line 1 "math/bit_ceil.hpp"



namespace m1une {
namespace math {

template <typename T>
constexpr T bit_ceil(T n) {
    if (n <= 1) return 1;
    T x = 1;
    while (x < n) x <<= 1;
    return x;
}

}  // namespace math
}  // 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 11 "ds/segtree/dual_segtree.hpp"

namespace m1une {
namespace ds {

// A generic Dual Segment Tree for range monoid updates and point queries.
template <m1une::monoid::IsMonoid Monoid>
struct DualSegtree {
    using T = typename Monoid::value_type;

   private:
    int _n, _size, _log;
    std::vector<T> _d;

    void all_apply(int k, const T& x) {
        _d[k] = Monoid::op(x, _d[k]);
    }

    void push(int k) {
        all_apply(2 * k, _d[k]);
        all_apply(2 * k + 1, _d[k]);
        _d[k] = Monoid::id();
    }

   public:
    // Constructs an empty dual segment tree.
    DualSegtree() : DualSegtree(0) {}

    // Constructs a dual segment tree of size `n`, initialized with the identity element.
    explicit DualSegtree(int n) : DualSegtree(std::vector<T>(n, Monoid::id())) {}

    // Constructs a dual segment tree from an existing vector.
    explicit DualSegtree(const std::vector<T>& v) : _n(int(v.size())) {
        _size = m1une::math::bit_ceil((unsigned int)(_n));
        _log = 0;
        while ((1U << _log) < (unsigned int)(_size)) _log++;
        _d.assign(2 * _size, Monoid::id());
        for (int i = 0; i < _n; i++) _d[_size + i] = v[i];
    }
    explicit DualSegtree(std::vector<T>&& v) : _n(int(v.size())) {
        _size = m1une::math::bit_ceil((unsigned int)(_n));
        _log = 0;
        while ((1U << _log) < (unsigned int)(_size)) _log++;
        _d.assign(2 * _size, Monoid::id());
        for (int i = 0; i < _n; i++) _d[_size + i] = std::move(v[i]);
    }

    // Constructs a dual segment tree 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 DualSegtree(const std::vector<U>& v) : _n(int(v.size())) {
        _size = m1une::math::bit_ceil((unsigned int)(_n));
        _log = 0;
        while ((1U << _log) < (unsigned int)(_size)) _log++;
        _d.assign(2 * _size, Monoid::id());
        for (int i = 0; i < _n; i++) {
            if constexpr (requires(U x) { Monoid::make(x); }) {
                _d[_size + i] = Monoid::make(v[i]);
            } else if constexpr (requires(U x, int idx) { Monoid::make(x, idx); }) {
                _d[_size + i] = Monoid::make(v[i], i);
            } else {
                _d[_size + i] = static_cast<T>(v[i]);
            }
        }
    }

    // Returns the number of elements.
    int size() const {
        return _n;
    }

    // Returns whether the tree is empty.
    bool empty() const {
        return _n == 0;
    }

    // Assigns x to the p-th element after applying pending updates on its path.
    void set(int p, T x) {
        assert(0 <= p && p < _n);
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        _d[p] = std::move(x);
    }

    // Returns the value of the p-th element after applying pending updates on its path.
    T get(int p) {
        assert(0 <= p && p < _n);
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        return _d[p];
    }

    // Returns the value of the p-th element.
    T operator[](int p) {
        return get(p);
    }

    // Applies x to the p-th element.
    void apply(int p, T x) {
        assert(0 <= p && p < _n);
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        all_apply(p, x);
    }

    // Applies x to all elements in the range [l, r).
    void apply(int l, int r, T x) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += _size;
        r += _size;

        for (int i = _log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        while (l < r) {
            if (l & 1) all_apply(l++, x);
            if (r & 1) all_apply(--r, x);
            l >>= 1;
            r >>= 1;
        }
    }

    // Returns all elements as a vector after applying all pending updates.
    std::vector<T> to_vector() {
        for (int k = 1; k < _size; k++) push(k);
        std::vector<T> res;
        res.reserve(_n);
        for (int i = 0; i < _n; i++) res.push_back(_d[_size + i]);
        return res;
    }

    // Returns the elements in the range [l, r) as a vector.
    std::vector<T> to_vector(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        std::vector<T> res;
        res.reserve(r - l);
        for (int i = l; i < r; i++) res.push_back(get(i));
        return res;
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

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

Dual Segment Tree
(ds/segtree/dual_segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Verified with

Code

Dual Segment Tree (ds/segtree/dual_segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Verified with

Code

Dual Segment Tree
(ds/segtree/dual_segtree.hpp)