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

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

登録された 2 次元点集合上で，矩形作用と一点取得を行う双対セグメント木．

DualSegmentTree2D<M> として使う．M は可換モノイドとする．

DualSegmentTree2D<M>(points)：取得されうる点集合 points で初期化する．重複は取り除かれる．
apply(xl, xr, yl, yr, f)：登録点 $(x,y)$ のうち $xl\leq x<xr,\ yl\leq y<yr$ を満たすものへ f を作用させる．
get(x, y)：登録済みの点 $(x,y)$ の値を返す．
contains(x, y)：点 $(x,y)$ が登録済みかを返す．

get する点は構築時に points に含まれている必要がある．

計算量

登録点数を $N$ とする．

構築：$O(N\log N)$
apply：$O(\log^2 N)$
get：$O(\log^2 N)$
空間：$O(N\log N)$

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

Depends on

Verified with

verify/segment-tree/LC_rectangle_add_point_get.dual_segment_tree_2d.test.cpp

Code

#pragma once

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

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

  DualSegmentTree2D() : n(0), size(1) {}
  explicit DualSegmentTree2D(const vector<pair<int, int>>& points) { build(points); }

  void build(vector<pair<int, int>> points) {
    sort(points.begin(), points.end());
    points.erase(unique(points.begin(), points.end()), points.end());
    ps = points;

    xs.clear();
    xs.reserve(ps.size());
    for (auto [x, _] : ps) xs.push_back(x);
    xs.erase(unique(xs.begin(), xs.end()), xs.end());

    n = xs.size();
    size = 1;
    while (size < n) size <<= 1;
    ys.assign(2 * size, {});
    seg.assign(2 * size, {});

    for (auto [x, y] : ps) {
      int k = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
      for (k += size; k > 0; k >>= 1) ys[k].push_back(y);
    }
    for (int k = 1; k < 2 * size; k++) {
      sort(ys[k].begin(), ys[k].end());
      ys[k].erase(unique(ys[k].begin(), ys[k].end()), ys[k].end());
      seg[k] = DualSegmentTree<M>((int)ys[k].size());
    }
  }

  bool contains(int x, int y) const {
    auto it = lower_bound(ps.begin(), ps.end(), make_pair(x, y));
    return it != ps.end() && *it == make_pair(x, y);
  }

  void apply(int xl, int xr, int yl, int yr, F f) {
    if (xl >= xr || yl >= yr) return;
    int l = lower_bound(xs.begin(), xs.end(), xl) - xs.begin();
    int r = lower_bound(xs.begin(), xs.end(), xr) - xs.begin();
    for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
      if (l & 1) apply_node(l++, yl, yr, f);
      if (r & 1) apply_node(--r, yl, yr, f);
    }
  }

  F get(int x, int y) {
    int k = leaf(x, y);
    F ret = M::e();
    while (k > 0) {
      ret = M::op(get_node(k, y), ret);
      k >>= 1;
    }
    return ret;
  }

  int size_x() const { return n; }
  int size_points() const { return ps.size(); }

 private:
  int n, size;
  vector<pair<int, int>> ps;
  vector<int> xs;
  vector<vector<int>> ys;
  vector<DualSegmentTree<M>> seg;

  int leaf(int x, int y) const {
    auto it = lower_bound(ps.begin(), ps.end(), make_pair(x, y));
    assert(it != ps.end() && *it == make_pair(x, y));
    int k = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    return k + size;
  }

  void apply_node(int k, int yl, int yr, F f) {
    int l = lower_bound(ys[k].begin(), ys[k].end(), yl) - ys[k].begin();
    int r = lower_bound(ys[k].begin(), ys[k].end(), yr) - ys[k].begin();
    seg[k].apply(l, r, f);
  }

  F get_node(int k, int y) {
    int i = lower_bound(ys[k].begin(), ys[k].end(), y) - ys[k].begin();
    assert(i < (int)ys[k].size() && ys[k][i] == y);
    return seg[k].get(i);
  }
};

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

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

template <class M>
REQUIRES(Monoid<M>)
struct DualSegmentTree {
  using F = typename M::value_type;

 private:
  int _n, size, log;
  vector<F> lz;

 public:
  DualSegmentTree() : DualSegmentTree(0) {}
  explicit DualSegmentTree(int n) : DualSegmentTree(vector<F>(n, M::e())) {}
  explicit DualSegmentTree(const vector<F> &v) : _n(int(v.size())) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    lz = vector<F>(2 * size, M::e());
    for (int i = 0; i < _n; i++) lz[size + i] = v[i];
  }
  void set(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i > 0; i--) push(p >> i);
    lz[p] = f;
  }
  F get(int p) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i > 0; i--) push(p >> i);
    return lz[p];
  }
  vector<F> all_get() {
    for (int i = 1; i < size; i++) push(i);
    return vector<F>(lz.begin() + size, lz.begin() + (size + _n));
  }
  void apply(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i > 0; i--) push(p >> i);
    inner_apply(p, f);
  }
  void apply(int l, int r, F f) {
    if (l >= r) return;
    assert(0 <= l && l <= r && r <= _n);
    l += size, r += size;
    for (int i = log; i > 0; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    while (l < r) {
      if ((l & 1) != 0) inner_apply(l++, f);
      if ((r & 1) != 0) inner_apply(--r, f);
      l >>= 1, r >>= 1;
    }
  }

 private:
  void push(int k) {
    inner_apply(2 * k, lz[k]);
    inner_apply(2 * k + 1, lz[k]);
    lz[k] = M::e();
  }
  void inner_apply(int k, F f) { lz[k] = M::op(f, lz[k]); }
};

/**
 * @brief Dual Segment Tree
 * @docs docs/segment-tree/dual-segment-tree.md
 */
#line 4 "segment-tree/dual-segment-tree-2d.hpp"

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

  DualSegmentTree2D() : n(0), size(1) {}
  explicit DualSegmentTree2D(const vector<pair<int, int>>& points) { build(points); }

  void build(vector<pair<int, int>> points) {
    sort(points.begin(), points.end());
    points.erase(unique(points.begin(), points.end()), points.end());
    ps = points;

    xs.clear();
    xs.reserve(ps.size());
    for (auto [x, _] : ps) xs.push_back(x);
    xs.erase(unique(xs.begin(), xs.end()), xs.end());

    n = xs.size();
    size = 1;
    while (size < n) size <<= 1;
    ys.assign(2 * size, {});
    seg.assign(2 * size, {});

    for (auto [x, y] : ps) {
      int k = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
      for (k += size; k > 0; k >>= 1) ys[k].push_back(y);
    }
    for (int k = 1; k < 2 * size; k++) {
      sort(ys[k].begin(), ys[k].end());
      ys[k].erase(unique(ys[k].begin(), ys[k].end()), ys[k].end());
      seg[k] = DualSegmentTree<M>((int)ys[k].size());
    }
  }

  bool contains(int x, int y) const {
    auto it = lower_bound(ps.begin(), ps.end(), make_pair(x, y));
    return it != ps.end() && *it == make_pair(x, y);
  }

  void apply(int xl, int xr, int yl, int yr, F f) {
    if (xl >= xr || yl >= yr) return;
    int l = lower_bound(xs.begin(), xs.end(), xl) - xs.begin();
    int r = lower_bound(xs.begin(), xs.end(), xr) - xs.begin();
    for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
      if (l & 1) apply_node(l++, yl, yr, f);
      if (r & 1) apply_node(--r, yl, yr, f);
    }
  }

  F get(int x, int y) {
    int k = leaf(x, y);
    F ret = M::e();
    while (k > 0) {
      ret = M::op(get_node(k, y), ret);
      k >>= 1;
    }
    return ret;
  }

  int size_x() const { return n; }
  int size_points() const { return ps.size(); }

 private:
  int n, size;
  vector<pair<int, int>> ps;
  vector<int> xs;
  vector<vector<int>> ys;
  vector<DualSegmentTree<M>> seg;

  int leaf(int x, int y) const {
    auto it = lower_bound(ps.begin(), ps.end(), make_pair(x, y));
    assert(it != ps.end() && *it == make_pair(x, y));
    int k = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    return k + size;
  }

  void apply_node(int k, int yl, int yr, F f) {
    int l = lower_bound(ys[k].begin(), ys[k].end(), yl) - ys[k].begin();
    int r = lower_bound(ys[k].begin(), ys[k].end(), yr) - ys[k].begin();
    seg[k].apply(l, r, f);
  }

  F get_node(int k, int y) {
    int i = lower_bound(ys[k].begin(), ys[k].end(), y) - ys[k].begin();
    assert(i < (int)ys[k].size() && ys[k][i] == y);
    return seg[k].get(i);
  }
};

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

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

計算量

Depends on

Verified with

Code

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