Segment Tree Beats
(segment-tree/segment-tree-beats.hpp)

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

Segment Tree Beats! のライブラリ．

簡単に言えば，現在見ているノードの情報だけでは作用が計算できない場合に子へ降りて再構築する lazy segment tree．

SegmentTreeBeats<A> として使う．A の形式と公開 API は LazySegmentTree<A> と同じだが，値モノイドの value_type は bool fail を持つ必要がある．

A::mapping(f, x) は，作用後の情報を x だけから計算できない場合に fail = true として返す．葉に対する作用は必ず成功しなければならない．

仕組み

通常の lazy segment tree では，作用 $f$ と値モノイドの演算 $\cdot$ に

\[f(x\cdot y)=f(x)\cdot f(y)\]

が成り立ち，集約した値へ直接作用できることを要求する．Segment Tree Beats ではこの計算が失敗することを許し，fail が立った節点の遅延値を子へ伝播して，左右の子から節点を再構築する．これにより基底の LazySegmentTree と問題固有の集約情報・作用を分離できる．

計算量は作用の失敗回数と，op，mapping，作用素の合成にかかる時間に依存する．これら 1 回の時間計算量の上界をそれぞれ $C_{\mathrm{op}}$，$C_{\mathrm{map}}$，$C_{\mathrm{comp}}$ とし，操作列全体で mapping が $K$ 回失敗するなら，通常の lazy segment tree の計算量に

\[O\left(K(C_{\mathrm{op}}+C_{\mathrm{map}}+C_{\mathrm{comp}})\right)\]

が加わる．利用時には，失敗のたびに値の種類数などが減少し，$K$ に十分小さい上界があることを確認する必要がある．

実装は以下の記事を参考にしている．

• atcoder::lazy_segtree に1行書き足すだけの抽象化 Segment Tree Beats

Depends on

• algebraic-structure/magma.hpp
• algebraic-structure/monoid-action.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp
• Lazy Segment Tree (segment-tree/lazy-segment-tree.hpp)

Required by

• Range Chmin Chmax Add Range Sum (segment-tree/range-chmin-chmax-add-range-sum.hpp)

Verified with

• verify/segment-tree/LC_range_chmin_chmax_add_range_sum.test.cpp

Code

#pragma once
#include "segment-tree/lazy-segment-tree.hpp"

template <class A>
REQUIRES(MonoidAction<A>)
struct SegmentTreeBeats : LazySegmentTree<A> {
  using base = LazySegmentTree<A>;
  using T = typename base::T;
  using F = typename base::F;

  SegmentTreeBeats() : base() {}
  explicit SegmentTreeBeats(int n) : base(n) {}
  explicit SegmentTreeBeats(const vector<T>& v) : base(v) {}

 protected:
  void all_apply(int k, F f) override {
    this->d[k] = A::mapping(f, this->d[k]);
    if (k < this->size) {
      this->lz[k] = base::OM::op(f, this->lz[k]);
      if (this->d[k].fail) this->push(k), this->update(k);
    }
  }
};

/**
 * @brief Segment Tree Beats
 * @docs docs/segment-tree/segment-tree-beats.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 3 "algebraic-structure/monoid-action.hpp"

#ifdef __cpp_concepts
template <class A>
concept MonoidAction = Monoid<typename A::value_monoid> && Monoid<typename A::operator_monoid> && requires(typename A::value_monoid::value_type x, typename A::operator_monoid::value_type f) {
  typename A::value_monoid;
  typename A::operator_monoid;
  { A::mapping(f, x) } -> same_as<typename A::value_monoid::value_type>;
};
#endif
#line 3 "segment-tree/lazy-segment-tree.hpp"

template <class A>
REQUIRES(MonoidAction<A>)
struct LazySegmentTree {
  using VM = typename A::value_monoid;
  using OM = typename A::operator_monoid;
  using T = typename VM::value_type;
  using F = typename OM::value_type;

 protected:
  int _n, size, log;
  vector<T> d;
  vector<F> lz;

  void update(int k) { d[k] = VM::op(d[2 * k], d[2 * k + 1]); }
  virtual void all_apply(int k, F f) {
    d[k] = A::mapping(f, d[k]);
    if (k < size) lz[k] = OM::op(f, lz[k]);
  }
  void push(int k) {
    all_apply(2 * k, lz[k]);
    all_apply(2 * k + 1, lz[k]);
    lz[k] = OM::e();
  }

 public:
  LazySegmentTree() : LazySegmentTree(0) {}
  explicit LazySegmentTree(int n) : LazySegmentTree(vector<T>(n, VM::e())) {}
  explicit LazySegmentTree(const vector<T>& v) : _n(int(v.size())) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    d = vector<T>(2 * size, VM::e());
    lz = vector<F>(size, OM::e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i > 0; i--) update(i);
  }
  virtual ~LazySegmentTree() = default;

  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] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  T get(int p) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return d[p];
  }
  T prod(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return VM::e();
    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);
    }
    T sml = VM::e(), smr = VM::e();
    while (l < r) {
      if (l & 1) sml = VM::op(sml, d[l++]);
      if (r & 1) smr = VM::op(d[--r], smr);
      l >>= 1, r >>= 1;
    }
    return VM::op(sml, smr);
  }
  T all_prod() { return d[1]; }
  void apply(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = A::mapping(f, d[p]);
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  void apply(int l, int r, F f) {
    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);
    }
    {
      int l2 = l, r2 = r;
      while (l < r) {
        if (l & 1) all_apply(l++, f);
        if (r & 1) all_apply(--r, f);
        l >>= 1, r >>= 1;
      }
      l = l2, r = r2;
    }
    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }
  template <bool (*g)(T)>
  int max_right(int l) {
    return max_right(l, [](T x) { return g(x); });
  }
  template <class G>
  int max_right(int l, G g) {
    assert(0 <= l && l <= _n);
    assert(g(VM::e()));
    if (l == _n) return _n;
    l += size;
    for (int i = log; i >= 1; i--) push(l >> i);
    T sm = VM::e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!g(VM::op(sm, d[l]))) {
        while (l < size) {
          push(l);
          l = (2 * l);
          if (g(VM::op(sm, d[l]))) sm = VM::op(sm, d[l++]);
        }
        return l - size;
      }
      sm = VM::op(sm, d[l++]);
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*g)(T)>
  int min_left(int r) {
    return min_left(r, [](T x) { return g(x); });
  }
  template <class G>
  int min_left(int r, G g) {
    assert(0 <= r && r <= _n);
    assert(g(VM::e()));
    if (r == 0) return 0;
    r += size;
    for (int i = log; i >= 1; i--) push((r - 1) >> i);
    T sm = VM::e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!g(VM::op(d[r], sm))) {
        while (r < size) {
          push(r);
          r = (2 * r + 1);
          if (g(VM::op(d[r], sm))) sm = VM::op(d[r--], sm);
        }
        return r + 1 - size;
      }
      sm = VM::op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }
};

/**
 * @brief Lazy Segment Tree
 * @docs docs/segment-tree/lazy-segment-tree.md
 */
#line 3 "segment-tree/segment-tree-beats.hpp"

template <class A>
REQUIRES(MonoidAction<A>)
struct SegmentTreeBeats : LazySegmentTree<A> {
  using base = LazySegmentTree<A>;
  using T = typename base::T;
  using F = typename base::F;

  SegmentTreeBeats() : base() {}
  explicit SegmentTreeBeats(int n) : base(n) {}
  explicit SegmentTreeBeats(const vector<T>& v) : base(v) {}

 protected:
  void all_apply(int k, F f) override {
    this->d[k] = A::mapping(f, this->d[k]);
    if (k < this->size) {
      this->lz[k] = base::OM::op(f, this->lz[k]);
      if (this->d[k].fail) this->push(k), this->update(k);
    }
  }
};

/**
 * @brief Segment Tree Beats
 * @docs docs/segment-tree/segment-tree-beats.md
 */

Back to top page