Dynamic Dual Segment Tree
(segment-tree/dynamic-dual-segment-tree.hpp)

• View this file on GitHub
• Last update: 2026-07-09 11:17:24+09:00
• Include: #include "segment-tree/dynamic-dual-segment-tree.hpp"

必要になったノードだけを作る双対セグメント木．

DynamicDualSegmentTree<M, I> として使う．M はモノイド，I は座標の型で，既定は long long．

• DynamicDualSegmentTree<M, I>(l, r)：座標範囲 $[l,r)$ で初期化する．
• apply(l, r, f)：各 $i\in[l,r)$ に対して $A_i\leftarrow f\cdot A_i$ とする．
• apply(p, f)：点 $p$ に対して $A_p\leftarrow f\cdot A_p$ とする．
• set(p, f)：点 $p$ の値を f にする．
• get(p)：点 $p$ の値を返す．
• node_count()：作られたノード数を返す．

初期値はすべて M::e() とみなす．

計算量

座標範囲の幅を $N$ とする．

• apply, set, get：$O(\log N)$

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

演算が非可換でも，新しい作用は左から掛かるものとして順序を保つ．

Depends on

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

Required by

• Dynamic 2D Dual Segment Tree (segment-tree/dynamic-dual-segment-tree-2d.hpp)

Verified with

• verify/segment-tree/LC_range_affine_point_get.dynamic_dual_segment_tree.test.cpp
• verify/segment-tree/LC_rectangle_add_point_get.dynamic_dual_segment_tree_2d.test.cpp

Code

#pragma once

#include "algebraic-structure/monoid.hpp"

template <class M, class I = long long>
REQUIRES(Monoid<M>)
struct DynamicDualSegmentTree {
  using F = typename M::value_type;

  DynamicDualSegmentTree() : DynamicDualSegmentTree(0, 1) {}
  DynamicDualSegmentTree(I l, I r) : low(l), high(r), root(0) {
    assert(low < high);
    nodes.push_back({});
  }

  void set(I p, F f) {
    assert(low <= p && p < high);
    root = set(root, low, high, p, f);
  }

  void apply(I p, F f) { apply(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);
  }

  F get(I p) const {
    assert(low <= p && p < high);
    return get(root, low, high, p);
  }

  int node_count() const { return (int)nodes.size() - 1; }

 private:
  struct Node {
    F lz = M::e();
    int l = 0, r = 0;
  };

  I low, high;
  int root;
  vector<Node> nodes;

  int new_node() {
    nodes.push_back({});
    return (int)nodes.size() - 1;
  }

  static I mid(I l, I r) { return l + (r - l) / 2; }
  void inner_apply(int t, F f) { nodes[t].lz = M::op(f, nodes[t].lz); }

  void push(int t) {
    if (nodes[t].l == 0) nodes[t].l = new_node();
    if (nodes[t].r == 0) nodes[t].r = new_node();
    inner_apply(nodes[t].l, nodes[t].lz);
    inner_apply(nodes[t].r, nodes[t].lz);
    nodes[t].lz = M::e();
  }

  int set(int t, I l, I r, I p, F f) {
    if (t == 0) t = new_node();
    if (r - l == 1) {
      nodes[t].lz = f;
      return t;
    }
    push(t);
    I m = mid(l, r);
    if (p < m)
      nodes[t].l = set(nodes[t].l, l, m, p, f);
    else
      nodes[t].r = set(nodes[t].r, m, r, p, f);
    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();
    if (ql <= l && r <= qr) {
      inner_apply(t, f);
      return t;
    }
    push(t);
    I m = mid(l, 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);
    return t;
  }

  F get(int t, I l, I r, I p) const {
    if (t == 0) return M::e();
    if (r - l == 1) return nodes[t].lz;
    I m = mid(l, r);
    F child = p < m ? get(nodes[t].l, l, m, p) : get(nodes[t].r, m, r, p);
    return M::op(nodes[t].lz, child);
  }
};

/**
 * @brief Dynamic Dual Segment Tree
 * @docs docs/segment-tree/dynamic-dual-segment-tree.md
 */

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

template <class M, class I = long long>
REQUIRES(Monoid<M>)
struct DynamicDualSegmentTree {
  using F = typename M::value_type;

  DynamicDualSegmentTree() : DynamicDualSegmentTree(0, 1) {}
  DynamicDualSegmentTree(I l, I r) : low(l), high(r), root(0) {
    assert(low < high);
    nodes.push_back({});
  }

  void set(I p, F f) {
    assert(low <= p && p < high);
    root = set(root, low, high, p, f);
  }

  void apply(I p, F f) { apply(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);
  }

  F get(I p) const {
    assert(low <= p && p < high);
    return get(root, low, high, p);
  }

  int node_count() const { return (int)nodes.size() - 1; }

 private:
  struct Node {
    F lz = M::e();
    int l = 0, r = 0;
  };

  I low, high;
  int root;
  vector<Node> nodes;

  int new_node() {
    nodes.push_back({});
    return (int)nodes.size() - 1;
  }

  static I mid(I l, I r) { return l + (r - l) / 2; }
  void inner_apply(int t, F f) { nodes[t].lz = M::op(f, nodes[t].lz); }

  void push(int t) {
    if (nodes[t].l == 0) nodes[t].l = new_node();
    if (nodes[t].r == 0) nodes[t].r = new_node();
    inner_apply(nodes[t].l, nodes[t].lz);
    inner_apply(nodes[t].r, nodes[t].lz);
    nodes[t].lz = M::e();
  }

  int set(int t, I l, I r, I p, F f) {
    if (t == 0) t = new_node();
    if (r - l == 1) {
      nodes[t].lz = f;
      return t;
    }
    push(t);
    I m = mid(l, r);
    if (p < m)
      nodes[t].l = set(nodes[t].l, l, m, p, f);
    else
      nodes[t].r = set(nodes[t].r, m, r, p, f);
    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();
    if (ql <= l && r <= qr) {
      inner_apply(t, f);
      return t;
    }
    push(t);
    I m = mid(l, 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);
    return t;
  }

  F get(int t, I l, I r, I p) const {
    if (t == 0) return M::e();
    if (r - l == 1) return nodes[t].lz;
    I m = mid(l, r);
    F child = p < m ? get(nodes[t].l, l, m, p) : get(nodes[t].r, m, r, p);
    return M::op(nodes[t].lz, child);
  }
};

/**
 * @brief Dynamic Dual Segment Tree
 * @docs docs/segment-tree/dynamic-dual-segment-tree.md
 */

Back to top page