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

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

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

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

• DynamicDualSegmentTree2D<M, I>(xl, xr, yl, yr)：座標範囲 $[xl,xr)\times[yl,yr)$ で初期化する．
• apply(xl, xr, yl, yr, f)：矩形 $[xl,xr)\times[yl,yr)$ に f を作用させる．
• get(x, y)：点 $(x,y)$ の値を返す．
• x_nodes()：作られた外側のノード数を返す．
• y_nodes()：作られた内側のノード数の合計を返す．

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

計算量

座標範囲の幅を $X,Y$ とする．

• apply：$O(\log X\log Y)$
• get：$O(\log X\log Y)$

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

2 次元版は矩形加算・一点取得のような可換な作用を想定している．

Depends on

• algebraic-structure/magma.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp
• Dynamic Dual Segment Tree (segment-tree/dynamic-dual-segment-tree.hpp)

Verified with

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

Code

#pragma once

#include "segment-tree/dynamic-dual-segment-tree.hpp"

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

  DynamicDualSegmentTree2D() : DynamicDualSegmentTree2D(0, 1, 0, 1) {}
  DynamicDualSegmentTree2D(I xl, I xr, I yl, I yr) : x_low(xl), x_high(xr), y_low(yl), y_high(yr), root(0) {
    assert(x_low < x_high);
    assert(y_low < y_high);
    xs.push_back({});
    ys.emplace_back(y_low, y_high);
  }

  void apply(I xl, I xr, I yl, I yr, F f) {
    assert(x_low <= xl && xl <= xr && xr <= x_high);
    assert(y_low <= yl && yl <= yr && yr <= y_high);
    if (xl == xr || yl == yr) return;
    root = apply_x(root, x_low, x_high, xl, xr, yl, yr, f);
  }

  F get(I x, I y) const {
    assert(x_low <= x && x < x_high);
    assert(y_low <= y && y < y_high);
    return get_x(root, x_low, x_high, x, y);
  }

  int x_nodes() const { return (int)xs.size() - 1; }
  int y_nodes() const {
    int ret = 0;
    for (const auto& seg : ys) ret += seg.node_count();
    return ret;
  }

 private:
  struct XNode {
    int l = 0, r = 0;
  };

  I x_low, x_high, y_low, y_high;
  int root;
  vector<XNode> xs;
  vector<DynamicDualSegmentTree<M, I>> ys;

  int new_x_node() {
    xs.push_back({});
    ys.emplace_back(y_low, y_high);
    return (int)xs.size() - 1;
  }

  static I mid(I l, I r) { return l + (r - l) / 2; }

  int apply_x(int t, I l, I r, I qxl, I qxr, I qyl, I qyr, F f) {
    if (qxr <= l || r <= qxl) return t;
    if (t == 0) t = new_x_node();
    if (qxl <= l && r <= qxr) {
      ys[t].apply(qyl, qyr, f);
      return t;
    }
    I m = mid(l, r);
    xs[t].l = apply_x(xs[t].l, l, m, qxl, qxr, qyl, qyr, f);
    xs[t].r = apply_x(xs[t].r, m, r, qxl, qxr, qyl, qyr, f);
    return t;
  }

  F get_x(int t, I l, I r, I x, I y) const {
    if (t == 0) return M::e();
    F cur = ys[t].get(y);
    if (r - l == 1) return cur;
    I m = mid(l, r);
    F child = x < m ? get_x(xs[t].l, l, m, x, y) : get_x(xs[t].r, m, r, x, y);
    return M::op(cur, child);
  }
};

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

#line 2 "segment-tree/dynamic-dual-segment-tree-2d.hpp"

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

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

  DynamicDualSegmentTree2D() : DynamicDualSegmentTree2D(0, 1, 0, 1) {}
  DynamicDualSegmentTree2D(I xl, I xr, I yl, I yr) : x_low(xl), x_high(xr), y_low(yl), y_high(yr), root(0) {
    assert(x_low < x_high);
    assert(y_low < y_high);
    xs.push_back({});
    ys.emplace_back(y_low, y_high);
  }

  void apply(I xl, I xr, I yl, I yr, F f) {
    assert(x_low <= xl && xl <= xr && xr <= x_high);
    assert(y_low <= yl && yl <= yr && yr <= y_high);
    if (xl == xr || yl == yr) return;
    root = apply_x(root, x_low, x_high, xl, xr, yl, yr, f);
  }

  F get(I x, I y) const {
    assert(x_low <= x && x < x_high);
    assert(y_low <= y && y < y_high);
    return get_x(root, x_low, x_high, x, y);
  }

  int x_nodes() const { return (int)xs.size() - 1; }
  int y_nodes() const {
    int ret = 0;
    for (const auto& seg : ys) ret += seg.node_count();
    return ret;
  }

 private:
  struct XNode {
    int l = 0, r = 0;
  };

  I x_low, x_high, y_low, y_high;
  int root;
  vector<XNode> xs;
  vector<DynamicDualSegmentTree<M, I>> ys;

  int new_x_node() {
    xs.push_back({});
    ys.emplace_back(y_low, y_high);
    return (int)xs.size() - 1;
  }

  static I mid(I l, I r) { return l + (r - l) / 2; }

  int apply_x(int t, I l, I r, I qxl, I qxr, I qyl, I qyr, F f) {
    if (qxr <= l || r <= qxl) return t;
    if (t == 0) t = new_x_node();
    if (qxl <= l && r <= qxr) {
      ys[t].apply(qyl, qyr, f);
      return t;
    }
    I m = mid(l, r);
    xs[t].l = apply_x(xs[t].l, l, m, qxl, qxr, qyl, qyr, f);
    xs[t].r = apply_x(xs[t].r, m, r, qxl, qxr, qyl, qyr, f);
    return t;
  }

  F get_x(int t, I l, I r, I x, I y) const {
    if (t == 0) return M::e();
    F cur = ys[t].get(y);
    if (r - l == 1) return cur;
    I m = mid(l, r);
    F child = x < m ? get_x(xs[t].l, l, m, x, y) : get_x(xs[t].r, m, r, x, y);
    return M::op(cur, child);
  }
};

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

Back to top page