Segment Tree
(algorithm/DataStructure/SegmentTree/segment_tree.hpp)

• View this file on GitHub
• Last update: 2025-07-06 12:46:03+09:00
• Include: #include "algorithm/DataStructure/SegmentTree/segment_tree.hpp"

概要

任意のモノイドを扱う「抽象セグメント木」．

あるモノイド $(S, \bullet: S \times S \rightarrow S, e \in S)$ において，長さ $N$ の要素列 $\lbrace a_0, a_1, \ldots, a_{n-1} \rbrace$ に対する次のクエリ処理を $\mathcal{O}(\log N)$ で行う．

• 一点更新：要素 $a_i$ を $x$ で更新する
• 区間取得：区間 $[l, r)$ の要素の総積 $a_l \bullet a_{l+1} \bullet \cdots \bullet a_{r-1}$ を取得する

ここで「モノイド (monoid)」とは，次の性質を満たす組 $(S, \bullet : S \times S \rightarrow S, e \in S)$ による代数的構造のことをいう．

1. 結合律：$(a \bullet b) \bullet c = a \bullet (b \bullet c) \quad (\forall a, \forall b, \forall c \in S)$
2. 単位元の存在：$e \bullet a = a \bullet e = a \quad (e \in S, \forall a \in S)$

例えば，自然数全体 $\mathbb{N}$ は加法に関して $0$ を単位元にもつモノイドを成す．

説明

algorithm::segment_tree::SegmentTree

テンプレート引数	説明
Monoid	モノイドの型．algorithm::algebra::Monoid を想定している．

コンストラクタ	説明	計算量
SegmentTree()	デフォルトコンストラクタ．サイズゼロの SegmentTree オブジェクトを構築する．	-
SegmentTree(n)	コンストラクタ．n 個の単位元 Monoid::one() で初期化された要素をもつ SegmentTree オブジェクトを構築する．	$\Theta(N)$
SegmentTree(n,a)	コンストラクタ．n 個の a で初期化された要素をもつ SegmentTree オブジェクトを構築する．	$\Theta(N)$
SegmentTree(first,last)	コンストラクタ．イテレータ範囲 [first,last) の要素を用いて SegmentTree オブジェクトを構築する．	$\Theta(N)$
SegmentTree(il)	初期化子リスト il を受け取るコンストラクタ．SegmentTree(il.begin(),il.end()) と等価．	$\Theta(N)$

メンバ関数	説明	計算量
x=size()	要素数 x を取得する．	$\mathcal{O}(1)$
set(k,a)	k 番目の要素を a に置き換える．	$\Theta(\log N)$
x=prod(k)	k 番目の要素 x を取得する．	$\mathcal{O}(1)$
x=prod(l,r)	区間 [l,r) の要素の総積 x を求める．	$\mathcal{O}(\log N)$
x=prod_all()	区間全体の要素の総積 x を求める．	$\mathcal{O}(1)$
r=most_right(l,pred)	pred(prod(l,r))==true となる区間の最右位置 r を二分探索する．ただし，区間 $[l,n)$ の要素は1項述語 pred によって区分化されていること．また，pred(Monoid::one())==true であること．	$\mathcal{O}(\log N)$
l=most_left(r,pred)	pred(prod(l,r))==true となる区間の最左位置 l を二分探索する．ただし，区間 $[l,n)$ の要素は1項述語 pred によって区分化されていること．また，pred(Monoid::one())==true であること．	$\mathcal{O}(\log N)$
reset()	全要素を単位元 Monoid::one() で初期化する．	$\Theta(N)$

参考

1. “SegTree”. AC Library. AtCoder. https://atcoder.github.io/ac-library/production/document_ja/segtree.html.
2. “モノイド”. Wikipedia. https://ja.wikipedia.org/wiki/モノイド.
3. rsk0315. “セグ木のお勉強を敬遠している人へ”. えびちゃんの日記. HatenaBlog. https://rsk0315.hatenablog.com/entry/2020/07/05/184929.
4. “セグメント木”. いかたこのたこつぼ. https://ikatakos.com/pot/programming_algorithm/data_structure/segment_tree.

Depends on

• Algebraic Structure（代数的構造） (algorithm/Math/Algebra/algebra.hpp)

Verified with

• verify/aoj-DSL_2_A-segment_tree.test.cpp
• verify/aoj-DSL_2_B-segment_tree.test.cpp
• verify/yosupo-point_add_range_sum-segment_tree.test.cpp
• verify/yosupo-point_set_range_composite-segment_tree.test.cpp

Code

#ifndef ALGORITHM_SEGMENT_TREE_HPP
#define ALGORITHM_SEGMENT_TREE_HPP 1

#include <algorithm>
#include <cassert>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <type_traits>
#include <vector>

#include "../../Math/Algebra/algebra.hpp"

namespace algorithm {

namespace segment_tree {

template <class Monoid>
class SegmentTree {
public:
    using monoid_type = Monoid;
    using value_type = monoid_type::value_type;

private:
    int m_sz;                         // m_sz:=(要素数).
    int m_n;                          // m_n:=(完全二分木の葉数).
    std::vector<monoid_type> m_tree;  // m_tree(2n)[]:=(完全二分木). 1-based index.

    void update(int k) { m_tree[k] = m_tree[k << 1] * m_tree[k << 1 | 1]; }
    void build() {
        for(int l = m_n >> 1, r = (m_n + m_sz - 1) >> 1; l >= 1; l >>= 1, r >>= 1) {
            for(int i = r; i >= l; --i) update(i);
        }
    }

public:
    // constructor. O(N).
    SegmentTree() : SegmentTree(0) {};
    explicit SegmentTree(int n) : m_sz(n), m_n(1) {
        assert(n >= 0);
        while(m_n < m_sz) m_n <<= 1;
        m_tree.assign(2 * m_n, monoid_type::one());
    }
    explicit SegmentTree(int n, const value_type &a) : SegmentTree(n, monoid_type(a)) {}
    explicit SegmentTree(int n, const monoid_type &a) : SegmentTree(n) {
        std::fill_n(m_tree.begin() + m_n, n, a);
        build();
    }
    template <std::input_iterator InputIter>
    explicit SegmentTree(InputIter first, InputIter last) : m_n(1), m_tree(first, last) {
        m_sz = m_tree.size();
        while(m_n < m_sz) m_n <<= 1;
        m_tree.reserve(2 * m_n);
        m_tree.insert(m_tree.begin(), m_n, monoid_type::one());
        m_tree.resize(2 * m_n, monoid_type::one());
        build();
    }
    template <typename T>
    explicit SegmentTree(std::initializer_list<T> il) : SegmentTree(il.begin(), il.end()) {}

    // 要素数を取得する．
    int size() const { return m_sz; }
    // k番目の要素をaに置き換える．O(log N).
    void set(int k, const value_type &a) { set(k, monoid_type(a)); }
    void set(int k, const monoid_type &a) {
        assert(0 <= k and k < size());
        k += m_n;
        m_tree[k] = a;
        while(k >>= 1) update(k);
    }
    // k番目の要素を取得する．O(1).
    value_type prod(int k) const {
        assert(0 <= k and k < size());
        return m_tree[k + m_n].value();
    }
    // 区間[l,r)の要素の総積を求める．O(log N).
    value_type prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= size());
        monoid_type &&val_l = monoid_type::one(), &&val_r = monoid_type::one();
        for(l += m_n, r += m_n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) val_l = val_l * m_tree[l++];
            if(r & 1) val_r = m_tree[--r] * val_r;
        }
        return (val_l * val_r).value();
    }
    // 区間全体の要素の総積を取得する．O(1).
    value_type prod_all() const { return m_tree[1].value(); }
    // pred(prod(l,r))==true となる区間の最右位値rを二分探索する．
    // ただし，区間[l,n)の要素はpred(S)によって区分化されていること．また，pred(e)==true であること．O(log N).
    template <bool (*pred)(value_type)>
    int most_right(int l) const {
        return most_right(l, [](const value_type &x) -> bool { return pred(x); });
    }
    template <typename Pred>
    int most_right(int l, Pred pred) const {
        static_assert(std::is_invocable_r<bool, Pred, value_type>::value);
        assert(0 <= l and l <= size());
        assert(pred(monoid_type::one().value()));
        if(l == m_sz) return m_sz;
        l += m_n;
        monoid_type &&val = monoid_type::one();
        do {
            while(!(l & 1)) l >>= 1;
            monoid_type &&tmp = val * m_tree[l];
            if(!pred(tmp.value())) {
                while(l < m_n) {
                    l <<= 1;
                    tmp = val * m_tree[l];
                    if(pred(tmp.value())) val = tmp, ++l;
                }
                return l - m_n;
            }
            val = tmp, ++l;
        } while((l & -l) != l);
        return m_sz;
    }
    // pred(prod(l,r))==true となる区間の最左位値lを二分探索する．
    // ただし，区間[0,r)の要素はpred(S)によって区分化されていること．また，pred(e)==true であること．O(log N).
    template <bool (*pred)(value_type)>
    int most_left(int r) const {
        return most_left(r, [](const value_type &x) -> bool { return pred(x); });
    }
    template <typename Pred>
    int most_left(int r, Pred pred) const {
        static_assert(std::is_invocable_r<bool, Pred, value_type>::value);
        assert(0 <= r and r <= size());
        assert(pred(monoid_type::one().value()));
        if(r == 0) return 0;
        r += m_n;
        monoid_type &&val = monoid_type::one();
        do {
            --r;
            while(r > 1 and (r & 1)) r >>= 1;
            monoid_type &&tmp = m_tree[r] * val;
            if(!pred(tmp.value())) {
                while(r < m_n) {
                    r = r << 1 | 1;
                    tmp = m_tree[r] * val;
                    if(pred(tmp.value())) val = tmp, --r;
                }
                return r + 1 - m_n;
            }
            val = tmp;
        } while((r & -r) != r);
        return 0;
    }
    void reset() { std::fill(m_tree.begin() + 1, m_tree.begin() + m_n + m_sz, monoid_type::one()); }

    friend std::ostream &operator<<(std::ostream &os, const SegmentTree &rhs) {
        os << "[\n";
        for(int l = 1, r = 2; r <= 2 * rhs.m_n; l <<= 1, r <<= 1) {
            for(int i = l; i < r; ++i) os << (i == l ? "  [" : " ") << rhs.m_tree[i].value();
            os << "]\n";
        }
        return os << "]";
    }
};

template <typename S>
using range_minimum_segment_tree = SegmentTree<algebra::monoid::minimum<S>>;

template <typename S>
using range_maximum_segment_tree = SegmentTree<algebra::monoid::maximum<S>>;

template <typename S>
using range_sum_segment_tree = SegmentTree<algebra::monoid::addition<S>>;

}  // namespace segment_tree

}  // namespace algorithm

#endif

#line 1 "algorithm/DataStructure/SegmentTree/segment_tree.hpp"



#include <algorithm>
#include <cassert>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <type_traits>
#include <vector>

#line 1 "algorithm/Math/Algebra/algebra.hpp"



#line 6 "algorithm/Math/Algebra/algebra.hpp"
#include <limits>
#include <numeric>
#line 9 "algorithm/Math/Algebra/algebra.hpp"
#include <utility>

namespace algorithm {

namespace algebra {

template <typename S>
class Set {
public:
    using value_type = S;

protected:
    value_type val;

public:
    constexpr Set() : val() {}
    constexpr Set(const value_type &val) : val(val) {}
    constexpr Set(value_type &&val) : val(std::move(val)) {}

    friend constexpr bool operator==(const Set &lhs, const Set &rhs) { return lhs.value() == rhs.value(); }
    friend std::istream &operator>>(std::istream &is, Set &rhs) { return is >> rhs.val; }
    friend std::ostream &operator<<(std::ostream &os, const Set &rhs) { return os << rhs.value(); }

    constexpr value_type value() const { return val; }
};

template <typename S, auto op>
class Semigroup : public Set<S> {
    static_assert(std::is_invocable_r<S, decltype(op), S, S>::value);

public:
    using base_type = Set<S>;
    using value_type = typename base_type::value_type;

    constexpr Semigroup() : base_type() {}
    constexpr Semigroup(const value_type &val) : base_type(val) {}
    constexpr Semigroup(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Semigroup operator*(const Semigroup &lhs, const Semigroup &rhs) { return Semigroup(op(lhs.value(), rhs.value())); }

    static constexpr auto get_op() { return op; }
};

template <typename S, auto op, auto e>
class Monoid : public Semigroup<S, op> {
    static_assert(std::is_invocable_r<S, decltype(e)>::value);

public:
    using base_type = Semigroup<S, op>;
    using value_type = typename base_type::value_type;

    constexpr Monoid() : base_type() {}
    constexpr Monoid(const value_type &val) : base_type(val) {}
    constexpr Monoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Monoid operator*(const Monoid &lhs, const Monoid &rhs) { return Monoid(op(lhs.value(), rhs.value())); }

    static constexpr auto get_e() { return e; }
    static constexpr Monoid one() { return Monoid(e()); }  // return identity element.
};

template <typename S, auto op, auto e, auto inverse>
class Group : public Monoid<S, op, e> {
    static_assert(std::is_invocable_r<S, decltype(inverse), S>::value);

public:
    using base_type = Monoid<S, op, e>;
    using value_type = typename base_type::value_type;

    constexpr Group() : base_type() {}
    constexpr Group(const value_type &val) : base_type(val) {}
    constexpr Group(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Group operator*(const Group &lhs, const Group &rhs) { return Group(op(lhs.value(), rhs.value())); }

    static constexpr auto get_inverse() { return inverse; }
    static constexpr Group one() { return Group(e()); }                    // return identity element.
    constexpr Group inv() const { return Group(inverse(this->value())); }  // return inverse element.
};

template <typename F, auto compose, auto id, typename X, auto mapping>
class OperatorMonoid : public Monoid<F, compose, id> {
    static_assert(std::is_invocable_r<X, decltype(mapping), F, X>::value);

public:
    using base_type = Monoid<F, compose, id>;
    using value_type = typename base_type::value_type;
    using acted_type = X;

    constexpr OperatorMonoid() : base_type() {}
    constexpr OperatorMonoid(const value_type &val) : base_type(val) {}
    constexpr OperatorMonoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr OperatorMonoid operator*(const OperatorMonoid &lhs, const OperatorMonoid &rhs) { return OperatorMonoid(compose(lhs.value(), rhs.value())); }

    static constexpr auto get_mapping() { return mapping; }
    static constexpr OperatorMonoid one() { return OperatorMonoid(id()); }  // return identity mapping.
    constexpr acted_type act(const acted_type &x) const { return mapping(this->value(), x); }
    template <class S>
    constexpr S act(const S &x) const {
        static_assert(std::is_base_of<Set<acted_type>, S>::value);
        return S(mapping(this->value(), x.value()));
    }
};

namespace element {

template <typename S>
constexpr auto zero = []() -> S { return S(); };

template <typename S>
constexpr auto one = []() -> S { return 1; };

template <typename S>
constexpr auto min = []() -> S { return std::numeric_limits<S>::min(); };

template <typename S>
constexpr auto max = []() -> S { return std::numeric_limits<S>::max(); };

template <typename S>
constexpr auto one_below_max = []() -> S { return std::numeric_limits<S>::max() - 1; };

template <typename S>
constexpr auto lowest = []() -> S { return std::numeric_limits<S>::lowest(); };

template <typename S>
constexpr auto one_above_lowest = []() -> S { return std::numeric_limits<S>::lowest() + 1; };

}  // namespace element

namespace unary_operator {

template <typename S>
constexpr auto identity = [](const S &val) -> S { return val; };

template <typename S>
constexpr auto negate = [](const S &val) -> S { return -val; };

}  // namespace unary_operator

namespace binary_operator {

template <typename T, typename S = T>
constexpr auto plus = [](const T &lhs, const S &rhs) -> S { return lhs + rhs; };

template <typename T, typename S = T>
constexpr auto mul = [](const T &lhs, const S &rhs) -> S { return lhs * rhs; };

template <typename T, typename S = T>
constexpr auto bit_and = [](const T &lhs, const S &rhs) -> S { return lhs & rhs; };

template <typename T, typename S = T>
constexpr auto bit_or = [](const T &lhs, const S &rhs) -> S { return lhs | rhs; };

template <typename T, typename S = T>
constexpr auto bit_xor = [](const T &lhs, const S &rhs) -> S { return lhs ^ rhs; };

template <typename T, typename S = T>
constexpr auto min = [](const T &lhs, const S &rhs) -> S { return std::min<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto max = [](const T &lhs, const S &rhs) -> S { return std::max<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto gcd = [](const T &lhs, const S &rhs) -> S { return std::gcd(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto lcm = [](const T &lhs, const S &rhs) -> S { return std::lcm(lhs, rhs); };

template <typename F, auto id, typename X = F>
constexpr auto assign_if_not_id = [](const F &lhs, const X &rhs) -> X {
    static_assert(std::is_invocable_r<F, decltype(id)>::value);
    return (lhs == id() ? rhs : lhs);
};

}  // namespace binary_operator

namespace monoid {

template <typename S>
using minimum = Monoid<S, binary_operator::min<S>, element::max<S>>;

template <typename S>
using minimum_safe = Monoid<S, binary_operator::min<S>, element::one_below_max<S>>;

template <typename S>
using maximum = Monoid<S, binary_operator::max<S>, element::lowest<S>>;

template <typename S>
using maximum_safe = Monoid<S, binary_operator::max<S>, element::one_above_lowest<S>>;

template <typename S>
using addition = Monoid<S, binary_operator::plus<S>, element::zero<S>>;

template <typename S>
using multiplication = Monoid<S, binary_operator::mul<S>, element::one<S>>;

template <typename S>
using bit_xor = Monoid<S, binary_operator::bit_xor<S>, element::zero<S>>;

}  // namespace monoid

namespace group {

template <typename S>
using addition = Group<S, binary_operator::plus<S>, element::zero<S>, unary_operator::negate<S>>;

template <typename S>
using bit_xor = Group<S, binary_operator::bit_xor<S>, element::zero<S>, unary_operator::identity<S>>;

}  // namespace group

namespace operator_monoid {

template <typename F, typename X = F>
using assign_for_minimum = OperatorMonoid<
    F, binary_operator::assign_if_not_id<F, element::max<F>>, element::max<F>,
    X, binary_operator::assign_if_not_id<F, element::max<F>, X>>;

template <typename F, typename X = F>
using assign_for_maximum = OperatorMonoid<
    F, binary_operator::assign_if_not_id<F, element::lowest<F>>, element::lowest<F>,
    X, binary_operator::assign_if_not_id<F, element::lowest<F>, X>>;

template <typename F, typename X = F>
using addition = OperatorMonoid<
    F, binary_operator::plus<F>, element::zero<F>,
    X, binary_operator::plus<F, X>>;

}  // namespace operator_monoid

}  // namespace algebra

}  // namespace algorithm


#line 13 "algorithm/DataStructure/SegmentTree/segment_tree.hpp"

namespace algorithm {

namespace segment_tree {

template <class Monoid>
class SegmentTree {
public:
    using monoid_type = Monoid;
    using value_type = monoid_type::value_type;

private:
    int m_sz;                         // m_sz:=(要素数).
    int m_n;                          // m_n:=(完全二分木の葉数).
    std::vector<monoid_type> m_tree;  // m_tree(2n)[]:=(完全二分木). 1-based index.

    void update(int k) { m_tree[k] = m_tree[k << 1] * m_tree[k << 1 | 1]; }
    void build() {
        for(int l = m_n >> 1, r = (m_n + m_sz - 1) >> 1; l >= 1; l >>= 1, r >>= 1) {
            for(int i = r; i >= l; --i) update(i);
        }
    }

public:
    // constructor. O(N).
    SegmentTree() : SegmentTree(0) {};
    explicit SegmentTree(int n) : m_sz(n), m_n(1) {
        assert(n >= 0);
        while(m_n < m_sz) m_n <<= 1;
        m_tree.assign(2 * m_n, monoid_type::one());
    }
    explicit SegmentTree(int n, const value_type &a) : SegmentTree(n, monoid_type(a)) {}
    explicit SegmentTree(int n, const monoid_type &a) : SegmentTree(n) {
        std::fill_n(m_tree.begin() + m_n, n, a);
        build();
    }
    template <std::input_iterator InputIter>
    explicit SegmentTree(InputIter first, InputIter last) : m_n(1), m_tree(first, last) {
        m_sz = m_tree.size();
        while(m_n < m_sz) m_n <<= 1;
        m_tree.reserve(2 * m_n);
        m_tree.insert(m_tree.begin(), m_n, monoid_type::one());
        m_tree.resize(2 * m_n, monoid_type::one());
        build();
    }
    template <typename T>
    explicit SegmentTree(std::initializer_list<T> il) : SegmentTree(il.begin(), il.end()) {}

    // 要素数を取得する．
    int size() const { return m_sz; }
    // k番目の要素をaに置き換える．O(log N).
    void set(int k, const value_type &a) { set(k, monoid_type(a)); }
    void set(int k, const monoid_type &a) {
        assert(0 <= k and k < size());
        k += m_n;
        m_tree[k] = a;
        while(k >>= 1) update(k);
    }
    // k番目の要素を取得する．O(1).
    value_type prod(int k) const {
        assert(0 <= k and k < size());
        return m_tree[k + m_n].value();
    }
    // 区間[l,r)の要素の総積を求める．O(log N).
    value_type prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= size());
        monoid_type &&val_l = monoid_type::one(), &&val_r = monoid_type::one();
        for(l += m_n, r += m_n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) val_l = val_l * m_tree[l++];
            if(r & 1) val_r = m_tree[--r] * val_r;
        }
        return (val_l * val_r).value();
    }
    // 区間全体の要素の総積を取得する．O(1).
    value_type prod_all() const { return m_tree[1].value(); }
    // pred(prod(l,r))==true となる区間の最右位値rを二分探索する．
    // ただし，区間[l,n)の要素はpred(S)によって区分化されていること．また，pred(e)==true であること．O(log N).
    template <bool (*pred)(value_type)>
    int most_right(int l) const {
        return most_right(l, [](const value_type &x) -> bool { return pred(x); });
    }
    template <typename Pred>
    int most_right(int l, Pred pred) const {
        static_assert(std::is_invocable_r<bool, Pred, value_type>::value);
        assert(0 <= l and l <= size());
        assert(pred(monoid_type::one().value()));
        if(l == m_sz) return m_sz;
        l += m_n;
        monoid_type &&val = monoid_type::one();
        do {
            while(!(l & 1)) l >>= 1;
            monoid_type &&tmp = val * m_tree[l];
            if(!pred(tmp.value())) {
                while(l < m_n) {
                    l <<= 1;
                    tmp = val * m_tree[l];
                    if(pred(tmp.value())) val = tmp, ++l;
                }
                return l - m_n;
            }
            val = tmp, ++l;
        } while((l & -l) != l);
        return m_sz;
    }
    // pred(prod(l,r))==true となる区間の最左位値lを二分探索する．
    // ただし，区間[0,r)の要素はpred(S)によって区分化されていること．また，pred(e)==true であること．O(log N).
    template <bool (*pred)(value_type)>
    int most_left(int r) const {
        return most_left(r, [](const value_type &x) -> bool { return pred(x); });
    }
    template <typename Pred>
    int most_left(int r, Pred pred) const {
        static_assert(std::is_invocable_r<bool, Pred, value_type>::value);
        assert(0 <= r and r <= size());
        assert(pred(monoid_type::one().value()));
        if(r == 0) return 0;
        r += m_n;
        monoid_type &&val = monoid_type::one();
        do {
            --r;
            while(r > 1 and (r & 1)) r >>= 1;
            monoid_type &&tmp = m_tree[r] * val;
            if(!pred(tmp.value())) {
                while(r < m_n) {
                    r = r << 1 | 1;
                    tmp = m_tree[r] * val;
                    if(pred(tmp.value())) val = tmp, --r;
                }
                return r + 1 - m_n;
            }
            val = tmp;
        } while((r & -r) != r);
        return 0;
    }
    void reset() { std::fill(m_tree.begin() + 1, m_tree.begin() + m_n + m_sz, monoid_type::one()); }

    friend std::ostream &operator<<(std::ostream &os, const SegmentTree &rhs) {
        os << "[\n";
        for(int l = 1, r = 2; r <= 2 * rhs.m_n; l <<= 1, r <<= 1) {
            for(int i = l; i < r; ++i) os << (i == l ? "  [" : " ") << rhs.m_tree[i].value();
            os << "]\n";
        }
        return os << "]";
    }
};

template <typename S>
using range_minimum_segment_tree = SegmentTree<algebra::monoid::minimum<S>>;

template <typename S>
using range_maximum_segment_tree = SegmentTree<algebra::monoid::maximum<S>>;

template <typename S>
using range_sum_segment_tree = SegmentTree<algebra::monoid::addition<S>>;

}  // namespace segment_tree

}  // namespace algorithm

Back to top page