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

• View this file on GitHub
• Last update: 2026-07-08 04:37:27+09:00
• Include: #include "segment-tree/dynamic-segment-tree.hpp"

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

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

• DynamicSegmentTree<M, I>(l, r)：座標範囲 $[l,r)$ で初期化する．
• set(p, v)：点 $p$ の値を v にする．
• apply(p, v)：点 $p$ の値を M::op(current, v) で更新する．
• get(p)：点 $p$ の値を返す．
• prod(l, r)：$[l,r)$ の値を集約する．
• all_prod()：全体を集約する．
• node_count()：作られたノード数を返す．

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

計算量

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

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

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

座標集合を事前に持てる場合は通常の SegmentTree や座標圧縮の方が速い． 巨大な座標範囲のごく一部だけを触る場合に使う．

Depends on

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

Required by

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

Verified with

• verify/segment-tree/LC_point_add_rectangle_sum.dynamic_segment_tree_2d.test.cpp
• verify/segment-tree/LC_point_set_range_composite_large_array.dynamic_segment_tree.test.cpp

Code

#pragma once

#include "algebraic-structure/monoid.hpp"

template <class M, class I = long long>
REQUIRES(Monoid<M>)
struct DynamicSegmentTree {
  using T = typename M::value_type;
  DynamicSegmentTree() : DynamicSegmentTree(0, 1) {}
  // [l, r)
  DynamicSegmentTree(I l, I r) : low(l), high(r), root(0) {
    assert(low < high);
    nodes.push_back({});
  }
  void set(I p, T v) {
    assert(low <= p && p < high);
    root = set(root, low, high, p, v);
  }
  void apply(I p, T v) {
    assert(low <= p && p < high);
    root = apply(root, low, high, p, v);
  }
  T get(I p) const {
    assert(low <= p && p < high);
    return prod(p, p + 1);
  }
  T prod(I l, I r) const {
    assert(low <= l && l <= r && r <= high);
    if (l == r) return M::e();
    return prod(root, low, high, l, r);
  }
  T all_prod() const { return value(root); }
  int node_count() const { return (int)nodes.size() - 1; }

 private:
  struct Node {
    T val = 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; }
  T value(int t) const { return t == 0 ? M::e() : nodes[t].val; }
  int set(int t, I l, I r, I p, T v) {
    if (t == 0) t = new_node();
    if (r - l == 1) {
      nodes[t].val = v;
      return t;
    }
    I m = mid(l, r);
    if (p < m)
      nodes[t].l = set(nodes[t].l, l, m, p, v);
    else
      nodes[t].r = set(nodes[t].r, m, r, p, v);
    nodes[t].val = M::op(value(nodes[t].l), value(nodes[t].r));
    return t;
  }
  int apply(int t, I l, I r, I p, T v) {
    if (t == 0) t = new_node();
    if (r - l == 1) {
      nodes[t].val = M::op(nodes[t].val, v);
      return t;
    }
    I m = mid(l, r);
    if (p < m)
      nodes[t].l = apply(nodes[t].l, l, m, p, v);
    else
      nodes[t].r = apply(nodes[t].r, m, r, p, v);
    nodes[t].val = M::op(value(nodes[t].l), value(nodes[t].r));
    return t;
  }
  T prod(int t, I l, I r, I ql, I qr) const {
    if (t == 0 || qr <= l || r <= ql) return M::e();
    if (ql <= l && r <= qr) return nodes[t].val;
    I m = mid(l, r);
    return M::op(prod(nodes[t].l, l, m, ql, qr), prod(nodes[t].r, m, r, ql, qr));
  }
};

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

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

template <class M, class I = long long>
REQUIRES(Monoid<M>)
struct DynamicSegmentTree {
  using T = typename M::value_type;
  DynamicSegmentTree() : DynamicSegmentTree(0, 1) {}
  // [l, r)
  DynamicSegmentTree(I l, I r) : low(l), high(r), root(0) {
    assert(low < high);
    nodes.push_back({});
  }
  void set(I p, T v) {
    assert(low <= p && p < high);
    root = set(root, low, high, p, v);
  }
  void apply(I p, T v) {
    assert(low <= p && p < high);
    root = apply(root, low, high, p, v);
  }
  T get(I p) const {
    assert(low <= p && p < high);
    return prod(p, p + 1);
  }
  T prod(I l, I r) const {
    assert(low <= l && l <= r && r <= high);
    if (l == r) return M::e();
    return prod(root, low, high, l, r);
  }
  T all_prod() const { return value(root); }
  int node_count() const { return (int)nodes.size() - 1; }

 private:
  struct Node {
    T val = 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; }
  T value(int t) const { return t == 0 ? M::e() : nodes[t].val; }
  int set(int t, I l, I r, I p, T v) {
    if (t == 0) t = new_node();
    if (r - l == 1) {
      nodes[t].val = v;
      return t;
    }
    I m = mid(l, r);
    if (p < m)
      nodes[t].l = set(nodes[t].l, l, m, p, v);
    else
      nodes[t].r = set(nodes[t].r, m, r, p, v);
    nodes[t].val = M::op(value(nodes[t].l), value(nodes[t].r));
    return t;
  }
  int apply(int t, I l, I r, I p, T v) {
    if (t == 0) t = new_node();
    if (r - l == 1) {
      nodes[t].val = M::op(nodes[t].val, v);
      return t;
    }
    I m = mid(l, r);
    if (p < m)
      nodes[t].l = apply(nodes[t].l, l, m, p, v);
    else
      nodes[t].r = apply(nodes[t].r, m, r, p, v);
    nodes[t].val = M::op(value(nodes[t].l), value(nodes[t].r));
    return t;
  }
  T prod(int t, I l, I r, I ql, I qr) const {
    if (t == 0 || qr <= l || r <= ql) return M::e();
    if (ql <= l && r <= qr) return nodes[t].val;
    I m = mid(l, r);
    return M::op(prod(nodes[t].l, l, m, ql, qr), prod(nodes[t].r, m, r, ql, qr));
  }
};

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

Back to top page