Dynamic Lazy Segment Tree
(segment-tree/dynamic-lazy-segment-tree.hpp)

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

必要になったノードだけを作る遅延伝播セグメント木．

DynamicLazySegmentTree<A, I> として使う．A は value_monoid, operator_monoid, mapping(f, x) を持つ作用を表す型，I は座標の型で，既定は long long．

• DynamicLazySegmentTree<A, I>(l, r)：座標範囲 $[l,r)$ で初期化する．初期値は全区間で value_monoid::e() とする．
• DynamicLazySegmentTree<A, I>(l, r, init)：座標範囲 $[l,r)$ で初期化する．init(a, b) は初期列の区間 $[a,b)$ の積を返す関数とする．
• set(p, x)：$A_p\gets x$ とする．
• get(p)：$A_p$ を取得する．
• apply(p, f)：$A_p\gets f A_p$ とする．
• apply(l, r, f)：各 $i\in[l,r)$ に対し $A_i\gets f A_i$ とする．
• prod(l, r)：$A_l\cdot A_{l+1}\cdot\cdots\cdot A_{r-1}$ を取得する．
• all_prod()：全体の積を取得する．
• node_count()：作られたノード数を返す．

init は任意の $l\leq m\leq r$ に対し次を満たす必要がある．

\[\mathrm{init}(l,r)=\mathrm{value\_monoid::op}(\mathrm{init}(l,m),\mathrm{init}(m,r))\]

計算量

座標範囲の幅を $N$ とし，init と各モノイド操作が $O(1)$ 時間であるとする．

• set, get, apply, prod：$O(\log N)$
• all_prod, node_count：$O(1)$

空間は，操作によって実際に作られたノード数に比例する．

Depends on

• algebraic-structure/magma.hpp
• algebraic-structure/monoid-action.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp

Verified with

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

Code

#pragma once

#include "algebraic-structure/monoid-action.hpp"

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

  DynamicLazySegmentTree() : DynamicLazySegmentTree(0, 1) {}
  DynamicLazySegmentTree(I l, I r) : DynamicLazySegmentTree(l, r, [](I, I) { return VM::e(); }) {}
  DynamicLazySegmentTree(I l, I r, function<T(I, I)> init) : low(l), high(r), root(0), initial(move(init)) {
    assert(low < high);
    nodes.push_back({});
  }

  void set(I p, T x) {
    assert(low <= p && p < high);
    root = set(root, low, high, p, x);
  }
  T get(I p) {
    assert(low <= p && p < high);
    return prod(p, p + 1);
  }
  T prod(I l, I r) {
    assert(low <= l && l <= r && r <= high);
    if (l == r) return VM::e();
    return prod(root, low, high, l, r);
  }
  T all_prod() const { return value(root, low, high); }
  void apply(I p, F f) {
    assert(low <= p && p < high);
    root = apply(root, low, high, p, p + 1, f);
  }
  void apply(I l, I r, F f) {
    assert(low <= l && l <= r && r <= high);
    if (l == r) return;
    root = apply(root, low, high, l, r, f);
  }
  int node_count() const { return (int)nodes.size() - 1; }

 private:
  struct Node {
    T val = VM::e();
    F lz = OM::e();
    int l = 0, r = 0;
  };

  I low, high;
  int root;
  function<T(I, I)> initial;
  vector<Node> nodes;

  int new_node(I l, I r) {
    nodes.push_back({initial(l, r), OM::e(), 0, 0});
    return (int)nodes.size() - 1;
  }
  static I mid(I l, I r) { return l + (r - l) / 2; }
  T value(int t, I l, I r) const { return t == 0 ? initial(l, r) : nodes[t].val; }
  void update(int t, I l, I m, I r) {
    nodes[t].val = VM::op(value(nodes[t].l, l, m), value(nodes[t].r, m, r));
  }
  void all_apply(int t, F f) {
    nodes[t].val = A::mapping(f, nodes[t].val);
    nodes[t].lz = OM::op(f, nodes[t].lz);
  }
  void push(int t, I l, I m, I r) {
    if (nodes[t].l == 0) nodes[t].l = new_node(l, m);
    if (nodes[t].r == 0) nodes[t].r = new_node(m, r);
    all_apply(nodes[t].l, nodes[t].lz);
    all_apply(nodes[t].r, nodes[t].lz);
    nodes[t].lz = OM::e();
  }
  int set(int t, I l, I r, I p, T x) {
    if (t == 0) t = new_node(l, r);
    if (r - l == 1) {
      nodes[t].val = x;
      nodes[t].lz = OM::e();
      return t;
    }
    I m = mid(l, r);
    push(t, l, m, r);
    if (p < m)
      nodes[t].l = set(nodes[t].l, l, m, p, x);
    else
      nodes[t].r = set(nodes[t].r, m, r, p, x);
    update(t, l, m, r);
    return t;
  }
  int apply(int t, I l, I r, I ql, I qr, F f) {
    if (qr <= l || r <= ql) return t;
    if (t == 0) t = new_node(l, r);
    if (ql <= l && r <= qr) {
      all_apply(t, f);
      return t;
    }
    I m = mid(l, r);
    push(t, l, m, r);
    nodes[t].l = apply(nodes[t].l, l, m, ql, qr, f);
    nodes[t].r = apply(nodes[t].r, m, r, ql, qr, f);
    update(t, l, m, r);
    return t;
  }
  T prod(int t, I l, I r, I ql, I qr) {
    if (qr <= l || r <= ql) return VM::e();
    if (t == 0) return initial(max(l, ql), min(r, qr));
    if (ql <= l && r <= qr) return nodes[t].val;
    I m = mid(l, r);
    push(t, l, m, r);
    return VM::op(prod(nodes[t].l, l, m, ql, qr), prod(nodes[t].r, m, r, ql, qr));
  }
};

/**
 * @brief Dynamic Lazy Segment Tree
 * @docs docs/segment-tree/dynamic-lazy-segment-tree.md
 */

#line 2 "segment-tree/dynamic-lazy-segment-tree.hpp"

#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 4 "segment-tree/dynamic-lazy-segment-tree.hpp"

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

  DynamicLazySegmentTree() : DynamicLazySegmentTree(0, 1) {}
  DynamicLazySegmentTree(I l, I r) : DynamicLazySegmentTree(l, r, [](I, I) { return VM::e(); }) {}
  DynamicLazySegmentTree(I l, I r, function<T(I, I)> init) : low(l), high(r), root(0), initial(move(init)) {
    assert(low < high);
    nodes.push_back({});
  }

  void set(I p, T x) {
    assert(low <= p && p < high);
    root = set(root, low, high, p, x);
  }
  T get(I p) {
    assert(low <= p && p < high);
    return prod(p, p + 1);
  }
  T prod(I l, I r) {
    assert(low <= l && l <= r && r <= high);
    if (l == r) return VM::e();
    return prod(root, low, high, l, r);
  }
  T all_prod() const { return value(root, low, high); }
  void apply(I p, F f) {
    assert(low <= p && p < high);
    root = apply(root, low, high, p, p + 1, f);
  }
  void apply(I l, I r, F f) {
    assert(low <= l && l <= r && r <= high);
    if (l == r) return;
    root = apply(root, low, high, l, r, f);
  }
  int node_count() const { return (int)nodes.size() - 1; }

 private:
  struct Node {
    T val = VM::e();
    F lz = OM::e();
    int l = 0, r = 0;
  };

  I low, high;
  int root;
  function<T(I, I)> initial;
  vector<Node> nodes;

  int new_node(I l, I r) {
    nodes.push_back({initial(l, r), OM::e(), 0, 0});
    return (int)nodes.size() - 1;
  }
  static I mid(I l, I r) { return l + (r - l) / 2; }
  T value(int t, I l, I r) const { return t == 0 ? initial(l, r) : nodes[t].val; }
  void update(int t, I l, I m, I r) {
    nodes[t].val = VM::op(value(nodes[t].l, l, m), value(nodes[t].r, m, r));
  }
  void all_apply(int t, F f) {
    nodes[t].val = A::mapping(f, nodes[t].val);
    nodes[t].lz = OM::op(f, nodes[t].lz);
  }
  void push(int t, I l, I m, I r) {
    if (nodes[t].l == 0) nodes[t].l = new_node(l, m);
    if (nodes[t].r == 0) nodes[t].r = new_node(m, r);
    all_apply(nodes[t].l, nodes[t].lz);
    all_apply(nodes[t].r, nodes[t].lz);
    nodes[t].lz = OM::e();
  }
  int set(int t, I l, I r, I p, T x) {
    if (t == 0) t = new_node(l, r);
    if (r - l == 1) {
      nodes[t].val = x;
      nodes[t].lz = OM::e();
      return t;
    }
    I m = mid(l, r);
    push(t, l, m, r);
    if (p < m)
      nodes[t].l = set(nodes[t].l, l, m, p, x);
    else
      nodes[t].r = set(nodes[t].r, m, r, p, x);
    update(t, l, m, r);
    return t;
  }
  int apply(int t, I l, I r, I ql, I qr, F f) {
    if (qr <= l || r <= ql) return t;
    if (t == 0) t = new_node(l, r);
    if (ql <= l && r <= qr) {
      all_apply(t, f);
      return t;
    }
    I m = mid(l, r);
    push(t, l, m, r);
    nodes[t].l = apply(nodes[t].l, l, m, ql, qr, f);
    nodes[t].r = apply(nodes[t].r, m, r, ql, qr, f);
    update(t, l, m, r);
    return t;
  }
  T prod(int t, I l, I r, I ql, I qr) {
    if (qr <= l || r <= ql) return VM::e();
    if (t == 0) return initial(max(l, ql), min(r, qr));
    if (ql <= l && r <= qr) return nodes[t].val;
    I m = mid(l, r);
    push(t, l, m, r);
    return VM::op(prod(nodes[t].l, l, m, ql, qr), prod(nodes[t].r, m, r, ql, qr));
  }
};

/**
 * @brief Dynamic Lazy Segment Tree
 * @docs docs/segment-tree/dynamic-lazy-segment-tree.md
 */

Back to top page