Segment Tree
(ds/segtree/segtree.hpp)

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

Overview

m1une::ds::Segtree is a generic segment tree for point updates and range queries. The query operation is supplied by a monoid, so the same data structure can handle sums, minimums, maximums, gcd, affine composition, and other associative operations.

Use it when updates affect one position at a time. For range updates, use LazySegtree with an acted monoid 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)

Ready-made monoids are available in monoid/.

Construction

Segtree(): creates an empty tree.
Segtree(int n): creates n elements initialized with Monoid::id().
Segtree(const std::vector<T>& v): builds from monoid values.
Segtree(std::vector<T>&& v): builds from moved monoid values.
Segtree(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.

All non-empty constructors build the tree in $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)`	Assigns `x` to index `p`.	$O(\log N)$
`T get(int p)`	Returns the value at index `p`.	$O(1)$
`T operator[](int p)`	Returns the value at index `p`.	$O(1)$
`T prod(int l, int r)`	Returns the monoid product over `[l, r)`.	$O(\log N)$
`T all_prod()`	Returns the product of the entire array.	$O(1)$
`std::vector<T> to_vector()`	Returns all elements as a vector.	$O(N)$
`std::vector<T> to_vector(int l, int r)`	Returns the elements in `[l, r)`.	$O(r - l)$
`int max_right<F>(int l, F f)`	Returns the largest `r` such that `f(prod(l, r))` is `true`. Requires `f(Monoid::id())`.	$O(\log N)$
`int min_left<F>(int r, F f)`	Returns the smallest `l` such that `f(prod(l, r))` is `true`. Requires `f(Monoid::id())`.	$O(\log N)$

Example

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

int main() {
    using Sum = m1une::monoid::Add<long long>;
    m1une::ds::Segtree<Sum> seg(std::vector<long long>{0, 0, 0, 0, 0});

    seg.set(0, 10);
    seg.set(2, 20);

    std::cout << seg.prod(0, 3) << "\n";  // 30

    return 0;
}

Depends on

Required by

Range Sort Range Composite (ds/range_query/range_sort_range_composite.hpp)

Verified with

Code

#ifndef M1UNE_SEGTREE_HPP
#define M1UNE_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 Segment Tree utilizing C++20 Concepts for type safety.
// It requires a Monoid struct that satisfies `m1une::monoid::IsMonoid`.
template <m1une::monoid::IsMonoid Monoid>
struct Segtree {
    using T = typename Monoid::value_type;

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

    void update(int k) {
        _d[k] = Monoid::op(_d[2 * k], _d[2 * k + 1]);
    }

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

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

    // Constructs a segment tree from an existing vector.
    explicit Segtree(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];
        for (int i = _size - 1; i >= 1; i--) update(i);
    }
    explicit Segtree(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]);
        for (int i = _size - 1; i >= 1; i--) update(i);
    }

    // Constructs a 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 Segtree(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]);
            }
        }
        for (int i = _size - 1; i >= 1; i--) update(i);
    }

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

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

    // Sets the value of the element at index `p` to `x`.
    void set(int p, T x) {
        assert(0 <= p && p < _n);
        p += _size;
        _d[p] = x;
        for (int i = 1; i <= _log; i++) update(p >> i);
    }

    // Returns the value of the element at index `p`.
    T get(int p) const {
        assert(0 <= p && p < _n);
        return _d[p + _size];
    }

    // Returns the value of the element at index `p`.
    T operator[](int p) const {
        return get(p);
    }

    // Returns the product (result of the monoid operation) in the range [l, r).
    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        T sml = Monoid::id(), smr = Monoid::id();
        l += _size;
        r += _size;
        while (l < r) {
            if (l & 1) sml = Monoid::op(sml, _d[l++]);
            if (r & 1) smr = Monoid::op(_d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return Monoid::op(sml, smr);
    }

    // Returns the product of the entire array.
    T all_prod() const {
        return _d[1];
    }

    // Returns all elements as a vector.
    std::vector<T> to_vector() const {
        return to_vector(0, _n);
    }

    // Returns the elements in the range [l, r) as a vector.
    std::vector<T> to_vector(int l, int r) const {
        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(_d[_size + i]);
        return res;
    }

    // Finds the largest `r` such that `f(prod(l, r))` is true.
    // Uses a custom functor or lambda `f`.
    template <class F>
    int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(Monoid::id()));
        if (l == _n) return _n;
        l += _size;
        T sm = Monoid::id();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(Monoid::op(sm, _d[l]))) {
                while (l < _size) {
                    l = (2 * l);
                    if (f(Monoid::op(sm, _d[l]))) {
                        sm = Monoid::op(sm, _d[l]);
                        l++;
                    }
                }
                return l - _size;
            }
            sm = Monoid::op(sm, _d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    // Finds the smallest `l` such that `f(prod(l, r))` is true.
    template <class F>
    int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(Monoid::id()));
        if (r == 0) return 0;
        r += _size;
        T sm = Monoid::id();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(Monoid::op(_d[r], sm))) {
                while (r < _size) {
                    r = (2 * r + 1);
                    if (f(Monoid::op(_d[r], sm))) {
                        sm = Monoid::op(_d[r], sm);
                        r--;
                    }
                }
                return r + 1 - _size;
            }
            sm = Monoid::op(_d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_SEGTREE_HPP

#line 1 "ds/segtree/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/segtree.hpp"

namespace m1une {
namespace ds {

// A generic Segment Tree utilizing C++20 Concepts for type safety.
// It requires a Monoid struct that satisfies `m1une::monoid::IsMonoid`.
template <m1une::monoid::IsMonoid Monoid>
struct Segtree {
    using T = typename Monoid::value_type;

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

    void update(int k) {
        _d[k] = Monoid::op(_d[2 * k], _d[2 * k + 1]);
    }

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

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

    // Constructs a segment tree from an existing vector.
    explicit Segtree(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];
        for (int i = _size - 1; i >= 1; i--) update(i);
    }
    explicit Segtree(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]);
        for (int i = _size - 1; i >= 1; i--) update(i);
    }

    // Constructs a 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 Segtree(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]);
            }
        }
        for (int i = _size - 1; i >= 1; i--) update(i);
    }

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

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

    // Sets the value of the element at index `p` to `x`.
    void set(int p, T x) {
        assert(0 <= p && p < _n);
        p += _size;
        _d[p] = x;
        for (int i = 1; i <= _log; i++) update(p >> i);
    }

    // Returns the value of the element at index `p`.
    T get(int p) const {
        assert(0 <= p && p < _n);
        return _d[p + _size];
    }

    // Returns the value of the element at index `p`.
    T operator[](int p) const {
        return get(p);
    }

    // Returns the product (result of the monoid operation) in the range [l, r).
    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        T sml = Monoid::id(), smr = Monoid::id();
        l += _size;
        r += _size;
        while (l < r) {
            if (l & 1) sml = Monoid::op(sml, _d[l++]);
            if (r & 1) smr = Monoid::op(_d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return Monoid::op(sml, smr);
    }

    // Returns the product of the entire array.
    T all_prod() const {
        return _d[1];
    }

    // Returns all elements as a vector.
    std::vector<T> to_vector() const {
        return to_vector(0, _n);
    }

    // Returns the elements in the range [l, r) as a vector.
    std::vector<T> to_vector(int l, int r) const {
        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(_d[_size + i]);
        return res;
    }

    // Finds the largest `r` such that `f(prod(l, r))` is true.
    // Uses a custom functor or lambda `f`.
    template <class F>
    int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(Monoid::id()));
        if (l == _n) return _n;
        l += _size;
        T sm = Monoid::id();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(Monoid::op(sm, _d[l]))) {
                while (l < _size) {
                    l = (2 * l);
                    if (f(Monoid::op(sm, _d[l]))) {
                        sm = Monoid::op(sm, _d[l]);
                        l++;
                    }
                }
                return l - _size;
            }
            sm = Monoid::op(sm, _d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    // Finds the smallest `l` such that `f(prod(l, r))` is true.
    template <class F>
    int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(Monoid::id()));
        if (r == 0) return 0;
        r += _size;
        T sm = Monoid::id();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(Monoid::op(_d[r], sm))) {
                while (r < _size) {
                    r = (2 * r + 1);
                    if (f(Monoid::op(_d[r], sm))) {
                        sm = Monoid::op(_d[r], sm);
                        r--;
                    }
                }
                return r + 1 - _size;
            }
            sm = Monoid::op(_d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

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

Segment Tree
(ds/segtree/segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Required by

Verified with

Code

Segment Tree (ds/segtree/segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Required by

Verified with

Code

Segment Tree
(ds/segtree/segtree.hpp)