挿入/削除の可能なセグメント木 (乱択二分探索木)
(binary-search-tree/rbst-segment-tree.hpp)

• View this file on GitHub
• Last update: 2026-08-26 13:48:57+09:00
• Include: #include "binary-search-tree/rbst-segment-tree.hpp"

乱択二分探索木により，列の挿入・削除・反転と区間積を処理する．

RBSTSegmentTree<M> として使う．M はモノイドを表す型とし，列を表す根 t は RBSTBase の操作と共通である．

• get(t, k)：$k$ 番目の値を返す．
• set(t, k, x)：$k$ 番目の値を $x$ とする．
• prod(t, l, r)：半開区間 $[l,r)$ の積を返す．空区間では M::e() を返す．
• reverse(t, l, r)：半開区間 $[l,r)$ を反転する．

RBSTBase の build，insert，erase，size，split，merge も利用できる．各操作の期待時間計算量は $O(\log N)$．

資料

• Library Checker: Range Reverse Range Sum

Depends on

• algebraic-structure/magma.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp
• Randomized Binary Search Tree (基底クラス) (binary-search-tree/rbst-base.hpp)

Verified with

• verify/binary-search-tree/LC_range_reverse_range_sum.rbst_segment_tree.test.cpp
• verify/binary-search-tree/UNIT_rbst_segment_tree.test.cpp

Code

#pragma once
#include "binary-search-tree/rbst-base.hpp"
#include "algebraic-structure/monoid.hpp"

template <class M>
REQUIRES(Monoid<M>)
struct RBSTSegmentTreeNode {
  using T = M::value_type;
  typename RBSTBase<RBSTSegmentTreeNode>::Ptr l, r;
  int cnt;
  T key, sum, rev_sum;
  bool rev;
  RBSTSegmentTreeNode(const T& t = M::e()) : l(), r(), cnt(1), key(t), sum(t), rev_sum(t), rev(false) {}
};

template <class M>
REQUIRES(Monoid<M>)
struct RBSTSegmentTree : RBSTBase<RBSTSegmentTreeNode<M>> {
  using T = M::value_type;
  using Node = RBSTSegmentTreeNode<M>;
  using base = RBSTBase<Node>;
  using base::merge;
  using base::split;
  using typename base::Ptr;

  RBSTSegmentTree() = default;
  T get(Ptr& t, int k) {
    auto x = split(t, k);
    auto y = split(x.second, 1);
    T v = y.first->key;
    t = merge(x.first, merge(y.first, y.second));
    return v;
  }
  void set(Ptr& t, int k, T v) {
    auto x = split(t, k);
    auto y = split(x.second, 1);
    y.first->key = v;
    update(y.first);
    t = merge(x.first, merge(y.first, y.second));
  }
  T prod(Ptr& t, int l, int r) {
    if (l >= r) return M::e();
    auto x = split(t, l);
    auto y = split(x.second, r - l);
    auto ret = y.first->sum;
    t = merge(x.first, merge(y.first, y.second));
    return ret;
  }
  void reverse(Ptr& t, int l, int r) {
    if (l >= r) return;
    auto x = split(t, l);
    auto y = split(x.second, r - l);
    toggle(y.first);
    t = merge(x.first, merge(y.first, y.second));
  }

 protected:
  Ptr update(Ptr t) override {
    t->cnt = 1;
    t->sum = t->rev_sum = t->key;
    if (t->l) {
      t->cnt += t->l->cnt;
      t->sum = M::op(t->l->sum, t->sum);
      t->rev_sum = M::op(t->rev_sum, t->l->rev_sum);
    }
    if (t->r) {
      t->cnt += t->r->cnt;
      t->sum = M::op(t->sum, t->r->sum);
      t->rev_sum = M::op(t->r->rev_sum, t->rev_sum);
    }
    return t;
  }
  void push(Ptr t) override {
    if (!t->rev) return;
    if (t->l) toggle(t->l);
    if (t->r) toggle(t->r);
    t->rev = false;
  }

 private:
  void toggle(Ptr t) {
    swap(t->l, t->r);
    swap(t->sum, t->rev_sum);
    t->rev ^= true;
  }
};

/**
 * @brief 挿入/削除の可能なセグメント木 (乱択二分探索木)
 * @docs docs/binary-search-tree/rbst-segment-tree.md
 */

#line 2 "binary-search-tree/rbst-base.hpp"

template <class Node>
struct RBSTBase {
  using Ptr = Node*;
  template <typename... Args>
  inline Ptr my_new(Args... args) {
    return new Node(args...);
  }
  inline void my_del(Ptr t) { delete t; }
  inline Ptr make_tree() const { return nullptr; }

  int size(Ptr t) const { return count(t); }
  Ptr merge(Ptr l, Ptr r) {
    if (!l || !r) return l ? l : r;
    if (int((rng() * (l->cnt + r->cnt)) >> 32) < l->cnt) {
      push(l);
      l->r = merge(l->r, r);
      return update(l);
    } else {
      push(r);
      r->l = merge(l, r->l);
      return update(r);
    }
  }
  pair<Ptr, Ptr> split(Ptr t, int k) {
    if (!t) return {nullptr, nullptr};
    push(t);
    if (k <= count(t->l)) {
      auto s = split(t->l, k);
      t->l = s.second;
      return {s.first, update(t)};
    } else {
      auto s = split(t->r, k - count(t->l) - 1);
      t->r = s.first;
      return {update(t), s.second};
    }
  }
  Ptr build(int l, int r, const vector<decltype(Node::key)>& v) {
    if (l + 1 == r) return my_new(v[l]);
    int m = (l + r) >> 1;
    Ptr pm = my_new(v[m]);
    if (l < m) pm->l = build(l, m, v);
    if (m + 1 < r) pm->r = build(m + 1, r, v);
    return update(pm);
  }
  Ptr build(const vector<decltype(Node::key)>& v) {
    return build(0, (int)v.size(), v);
  }
  template <typename... Args>
  void insert(Ptr& t, int k, const Args&... args) {
    auto x = split(t, k);
    t = merge(merge(x.first, my_new(args...)), x.second);
  }
  void erase(Ptr& t, int k) {
    auto x = split(t, k);
    auto y = split(x.second, 1);
    my_del(y.first);
    t = merge(x.first, y.second);
  }

 protected:
  static uint64_t rng() {
    static uint64_t x_ = 123456789ull;
    return x_ ^= x_ << 7, x_ ^= x_ >> 9, x_ & 0xFFFFFFFFull;
  }
  inline int count(const Ptr t) const { return t ? t->cnt : 0; }
  virtual void push(Ptr) = 0;
  virtual Ptr update(Ptr) = 0;
};

/**
 * @brief Randomized Binary Search Tree (基底クラス)
 * @docs docs/binary-search-tree/rbst-base.md
 */
#line 2 "algebraic-structure/util.hpp"
#ifdef __cpp_concepts
#define REQUIRES(...) requires __VA_ARGS__
#else
#define REQUIRES(...)
#endif
#line 3 "algebraic-structure/magma.hpp"

#ifdef __cpp_concepts
template <class M>
concept Magma = requires(typename M::value_type x, typename M::value_type y) {
  typename M::value_type;
  { M::op(x, y) } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMagma {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
};
template <class T>
struct MulMagma {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
};
template <class T, T id>
struct MaxMagma {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
};
template <class T, T id>
struct MinMagma {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
};
#line 3 "algebraic-structure/monoid.hpp"

#ifdef __cpp_concepts
template <class M>
concept Monoid = Magma<M> && requires {
  { M::e() } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMonoid {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
};
template <class T>
struct MulMonoid {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
};
template <class T, T id>
struct MaxMonoid {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
  static T e() { return id; }
};
template <class T, T id>
struct MinMonoid {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
  static T e() { return id; }
};
#line 4 "binary-search-tree/rbst-segment-tree.hpp"

template <class M>
REQUIRES(Monoid<M>)
struct RBSTSegmentTreeNode {
  using T = M::value_type;
  typename RBSTBase<RBSTSegmentTreeNode>::Ptr l, r;
  int cnt;
  T key, sum, rev_sum;
  bool rev;
  RBSTSegmentTreeNode(const T& t = M::e()) : l(), r(), cnt(1), key(t), sum(t), rev_sum(t), rev(false) {}
};

template <class M>
REQUIRES(Monoid<M>)
struct RBSTSegmentTree : RBSTBase<RBSTSegmentTreeNode<M>> {
  using T = M::value_type;
  using Node = RBSTSegmentTreeNode<M>;
  using base = RBSTBase<Node>;
  using base::merge;
  using base::split;
  using typename base::Ptr;

  RBSTSegmentTree() = default;
  T get(Ptr& t, int k) {
    auto x = split(t, k);
    auto y = split(x.second, 1);
    T v = y.first->key;
    t = merge(x.first, merge(y.first, y.second));
    return v;
  }
  void set(Ptr& t, int k, T v) {
    auto x = split(t, k);
    auto y = split(x.second, 1);
    y.first->key = v;
    update(y.first);
    t = merge(x.first, merge(y.first, y.second));
  }
  T prod(Ptr& t, int l, int r) {
    if (l >= r) return M::e();
    auto x = split(t, l);
    auto y = split(x.second, r - l);
    auto ret = y.first->sum;
    t = merge(x.first, merge(y.first, y.second));
    return ret;
  }
  void reverse(Ptr& t, int l, int r) {
    if (l >= r) return;
    auto x = split(t, l);
    auto y = split(x.second, r - l);
    toggle(y.first);
    t = merge(x.first, merge(y.first, y.second));
  }

 protected:
  Ptr update(Ptr t) override {
    t->cnt = 1;
    t->sum = t->rev_sum = t->key;
    if (t->l) {
      t->cnt += t->l->cnt;
      t->sum = M::op(t->l->sum, t->sum);
      t->rev_sum = M::op(t->rev_sum, t->l->rev_sum);
    }
    if (t->r) {
      t->cnt += t->r->cnt;
      t->sum = M::op(t->sum, t->r->sum);
      t->rev_sum = M::op(t->r->rev_sum, t->rev_sum);
    }
    return t;
  }
  void push(Ptr t) override {
    if (!t->rev) return;
    if (t->l) toggle(t->l);
    if (t->r) toggle(t->r);
    t->rev = false;
  }

 private:
  void toggle(Ptr t) {
    swap(t->l, t->r);
    swap(t->sum, t->rev_sum);
    t->rev ^= true;
  }
};

/**
 * @brief 挿入/削除の可能なセグメント木 (乱択二分探索木)
 * @docs docs/binary-search-tree/rbst-segment-tree.md
 */

Back to top page