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

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

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

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

DynamicSegmentTree2D<M, I>(xl, xr, yl, yr)：座標範囲 $[xl,xr)\times[yl,yr)$ で初期化する．
set(x, y, v)：点 $(x,y)$ の値を v にする．
apply(x, y, v)：点 $(x,y)$ にある値を M::op(current, v) で更新する．
get(x, y)：点 $(x,y)$ の値を返す．
prod(xl, xr, yl, yr)：$xl\leq x<xr,\ yl\leq y<yr$ の値を集約する．
x_nodes()：作られた外側のノード数を返す．
y_nodes()：作られた内側のノード数を返す．

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

計算量

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

set, apply：$O(\log X\log Y)$
get：$O(\log X\log Y)$
prod：$O(\log X\log Y)$

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

使い分け

更新される点を事前に列挙できる場合は SegmentTree2D の方が速く，メモリも読みやすい．座標集合を事前に持てない場合や，巨大な座標空間のごく一部だけを触る場合はこちらを使う．

Depends on

Verified with

verify/segment-tree/LC_point_add_rectangle_sum.dynamic_segment_tree_2d.test.cpp

Code

#pragma once

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

// M: commutative monoid
template <class M, class I = long long>
REQUIRES(Monoid<M>)
struct DynamicSegmentTree2D {
  using T = typename M::value_type;
  DynamicSegmentTree2D() : DynamicSegmentTree2D(0, 1, 0, 1) {}
  // [xl, xr) * [yl, yr)
  DynamicSegmentTree2D(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 set(I x, I y, T v) {
    assert(x_low <= x && x < x_high);
    assert(y_low <= y && y < y_high);
    root = set_x(root, x_low, x_high, x, y, v);
  }
  void apply(I x, I y, T v) {
    assert(x_low <= x && x < x_high);
    assert(y_low <= y && y < y_high);
    root = apply_x(root, x_low, x_high, x, y, v);
  }
  T get(I x, I y) const {
    assert(x_low <= x && x < x_high);
    assert(y_low <= y && y < y_high);
    return prod(x, x + 1, y, y + 1);
  }
  T prod(I qxl, I qxr, I qyl, I qyr) const {
    assert(x_low <= qxl && qxl <= qxr && qxr <= x_high);
    assert(y_low <= qyl && qyl <= qyr && qyr <= y_high);
    if (qxl == qxr || qyl == qyr) return M::e();
    return prod_x(root, x_low, x_high, qxl, qxr, qyl, qyr);
  }
  int x_nodes() const { return 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<DynamicSegmentTree<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; }
  T get_y(int t, I y) const {
    return t == 0 ? M::e() : ys[t].get(y);
  }
  int set_x(int t, I l, I r, I x, I y, T v) {
    if (t == 0) t = new_x_node();
    if (r - l == 1) {
      ys[t].set(y, v);
      return t;
    }
    I m = mid(l, r);
    if (x < m)
      xs[t].l = set_x(xs[t].l, l, m, x, y, v);
    else
      xs[t].r = set_x(xs[t].r, m, r, x, y, v);
    ys[t].set(y, M::op(get_y(xs[t].l, y), get_y(xs[t].r, y)));
    return t;
  }
  int apply_x(int t, I l, I r, I x, I y, T v) {
    if (t == 0) t = new_x_node();
    ys[t].apply(y, v);
    if (r - l == 1) return t;
    I m = mid(l, r);
    if (x < m)
      xs[t].l = apply_x(xs[t].l, l, m, x, y, v);
    else
      xs[t].r = apply_x(xs[t].r, m, r, x, y, v);
    return t;
  }
  T prod_x(int t, I l, I r, I qxl, I qxr, I qyl, I qyr) const {
    if (t == 0 || qxr <= l || r <= qxl) return M::e();
    if (qxl <= l && r <= qxr) return ys[t].prod(qyl, qyr);
    I m = mid(l, r);
    return M::op(prod_x(xs[t].l, l, m, qxl, qxr, qyl, qyr), prod_x(xs[t].r, m, r, qxl, qxr, qyl, qyr));
  }
};

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

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

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

// M: commutative monoid
template <class M, class I = long long>
REQUIRES(Monoid<M>)
struct DynamicSegmentTree2D {
  using T = typename M::value_type;
  DynamicSegmentTree2D() : DynamicSegmentTree2D(0, 1, 0, 1) {}
  // [xl, xr) * [yl, yr)
  DynamicSegmentTree2D(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 set(I x, I y, T v) {
    assert(x_low <= x && x < x_high);
    assert(y_low <= y && y < y_high);
    root = set_x(root, x_low, x_high, x, y, v);
  }
  void apply(I x, I y, T v) {
    assert(x_low <= x && x < x_high);
    assert(y_low <= y && y < y_high);
    root = apply_x(root, x_low, x_high, x, y, v);
  }
  T get(I x, I y) const {
    assert(x_low <= x && x < x_high);
    assert(y_low <= y && y < y_high);
    return prod(x, x + 1, y, y + 1);
  }
  T prod(I qxl, I qxr, I qyl, I qyr) const {
    assert(x_low <= qxl && qxl <= qxr && qxr <= x_high);
    assert(y_low <= qyl && qyl <= qyr && qyr <= y_high);
    if (qxl == qxr || qyl == qyr) return M::e();
    return prod_x(root, x_low, x_high, qxl, qxr, qyl, qyr);
  }
  int x_nodes() const { return 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<DynamicSegmentTree<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; }
  T get_y(int t, I y) const {
    return t == 0 ? M::e() : ys[t].get(y);
  }
  int set_x(int t, I l, I r, I x, I y, T v) {
    if (t == 0) t = new_x_node();
    if (r - l == 1) {
      ys[t].set(y, v);
      return t;
    }
    I m = mid(l, r);
    if (x < m)
      xs[t].l = set_x(xs[t].l, l, m, x, y, v);
    else
      xs[t].r = set_x(xs[t].r, m, r, x, y, v);
    ys[t].set(y, M::op(get_y(xs[t].l, y), get_y(xs[t].r, y)));
    return t;
  }
  int apply_x(int t, I l, I r, I x, I y, T v) {
    if (t == 0) t = new_x_node();
    ys[t].apply(y, v);
    if (r - l == 1) return t;
    I m = mid(l, r);
    if (x < m)
      xs[t].l = apply_x(xs[t].l, l, m, x, y, v);
    else
      xs[t].r = apply_x(xs[t].r, m, r, x, y, v);
    return t;
  }
  T prod_x(int t, I l, I r, I qxl, I qxr, I qyl, I qyr) const {
    if (t == 0 || qxr <= l || r <= qxl) return M::e();
    if (qxl <= l && r <= qxr) return ys[t].prod(qyl, qyr);
    I m = mid(l, r);
    return M::op(prod_x(xs[t].l, l, m, qxl, qxr, qyl, qyr), prod_x(xs[t].r, m, r, qxl, qxr, qyl, qyr));
  }
};

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

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

計算量

使い分け

Depends on

Verified with

Code

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