Range Tree (領域木) (structure/segment-tree/range-tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-08-10 03:11:07+09:00
• Include: #include "structure/segment-tree/range-tree.hpp"

領域木は、セグメント木のノードにデータ構造をのせることで、二次元クエリを処理できるデータ構造です。

ある点に対する重みの加算と、矩形領域の点の重みの総和を求めたい場合は、Wavelet Matrix Point Add Rectangle Sum を用いた方が定数倍が高速です。

コンストラクタ

RangeTree< K, Monoid2D >(Monoid2D m)

Monoid2D m の領域木をつくります。K は座標の型です。

計算量

• $O(1)$

Monoid2D について

Monoid2D は、次の構造体と関数を持つ構造体です。

template< typename T >
struct Monoid2D {
  using S = ?;
  using D = ?;
  static constexpr S op(const S& a, const S& b) {}
  static constexpr S e() {}
  static constexpr D init(int n) {}
  static constexpr void apply(D& d, int k, const S& v) {}
  static constexpr S prod(D& d, int l, int r) {}
};

• 型 S
• セグメント木のノードにのせるデータ構造の型 D
• 二項演算 S op(S a, S b)
• 単位元 e()
• データ構造をサイズ n で初期化するための関数 D init(n)
• データ構造 d の k 番目の要素を v で更新するための関数 apply(d, k, v)
• データ構造 d の区間 [l, r) を畳み込む演算 S prod(d, l, r)

add_point

void add_point(K x, K y)

点 $(x, y)$ を追加します。

計算量

• $O(1)$

build

void build()

領域木を構築します。add_point ですべての点を追加したあとに呼び出します。

計算量

• $O(n \log n)$

apply

void apply(K x, K y, S a)

点 (x, y) の要素を a で更新します。

制約

• build() をすでに呼び出している
• $(x, y)$ は add_point で追加された点

計算量

• $O(f(n) \log n)$

$f(n)$ は Monoid2D の apply の計算量です。

prod

S prod(K l, K d, K r, K u)

$l \leq x \lt r$ かつ $d \leq y \lt u$ を満たす点 $(x, y)$ に対して二項演算した結果を返します。

制約

• build() をすでに呼び出している

計算量

• $O(g(n) \log n)$

$g(n)$ は Monoid2D の prod の計算量です。

Verified with

• test/verify/yosupo-point-add-rectangle-sum-4.test.cpp

Code

template <typename K, typename Monoid2D>
struct RangeTree {
  using S = typename Monoid2D::S;
  using D = typename Monoid2D::D;

 private:
  vector<vector<K> > ys;
  vector<pair<K, K> > ps;
  vector<K> xs;
  vector<D> ds;
  int n;

  Monoid2D m;

  int id(K x) const {
    return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
  }

  int id(int k, K y) const {
    return lower_bound(ys[k].begin(), ys[k].end(), y) - ys[k].begin();
  }

 public:
  RangeTree() = default;

  explicit RangeTree(Monoid2D m) : m(m) {}

  void add_point(K x, K y) { ps.emplace_back(x, y); }

  void build() {
    sort(ps.begin(), ps.end());
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    n = (int)ps.size();
    xs.reserve(n);
    for (auto& [x, _] : ps) {
      xs.emplace_back(x);
    }
    ys.resize(2 * n);
    ds.resize(2 * n);
    for (int i = 0; i < n; i++) {
      ys[i + n] = {ps[i].second};
      ds[i + n] = m.init(1);
    }
    for (int i = n - 1; i > 0; i--) {
      ys[i].resize(ys[i << 1].size() + ys[(i << 1) | 1].size());
      merge(ys[i << 1].begin(), ys[i << 1].end(), ys[(i << 1) | 1].begin(),
            ys[(i << 1) | 1].end(), ys[i].begin());
      ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
      ds[i] = m.init((int)ys[i].size());
    }
  }

  void apply(K x, K y, S a) {
    int k = lower_bound(ps.begin(), ps.end(), make_pair(x, y)) - ps.begin();
    assert(ps[k] == make_pair(x, y));
    k += n;
    while (k > 0) {
      m.apply(ds[k], id(k, y), a);
      k >>= 1;
    }
  }

  S prod(K l, K d, K r, K u) {
    int a = id(l), b = id(r);
    a += n;
    b += n;
    S L = m.e(), R = m.e();
    while (a < b) {
      if (a & 1) {
        L = m.op(L, m.prod(ds[a], id(a, d), id(a, u)));
        ++a;
      }
      if (b & 1) {
        --b;
        R = m.op(m.prod(ds[b], id(b, d), id(b, u)), R);
      }
      a >>= 1;
      b >>= 1;
    }
    return m.op(L, R);
  }
};

#line 1 "structure/segment-tree/range-tree.hpp"
template <typename K, typename Monoid2D>
struct RangeTree {
  using S = typename Monoid2D::S;
  using D = typename Monoid2D::D;

 private:
  vector<vector<K> > ys;
  vector<pair<K, K> > ps;
  vector<K> xs;
  vector<D> ds;
  int n;

  Monoid2D m;

  int id(K x) const {
    return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
  }

  int id(int k, K y) const {
    return lower_bound(ys[k].begin(), ys[k].end(), y) - ys[k].begin();
  }

 public:
  RangeTree() = default;

  explicit RangeTree(Monoid2D m) : m(m) {}

  void add_point(K x, K y) { ps.emplace_back(x, y); }

  void build() {
    sort(ps.begin(), ps.end());
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    n = (int)ps.size();
    xs.reserve(n);
    for (auto& [x, _] : ps) {
      xs.emplace_back(x);
    }
    ys.resize(2 * n);
    ds.resize(2 * n);
    for (int i = 0; i < n; i++) {
      ys[i + n] = {ps[i].second};
      ds[i + n] = m.init(1);
    }
    for (int i = n - 1; i > 0; i--) {
      ys[i].resize(ys[i << 1].size() + ys[(i << 1) | 1].size());
      merge(ys[i << 1].begin(), ys[i << 1].end(), ys[(i << 1) | 1].begin(),
            ys[(i << 1) | 1].end(), ys[i].begin());
      ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
      ds[i] = m.init((int)ys[i].size());
    }
  }

  void apply(K x, K y, S a) {
    int k = lower_bound(ps.begin(), ps.end(), make_pair(x, y)) - ps.begin();
    assert(ps[k] == make_pair(x, y));
    k += n;
    while (k > 0) {
      m.apply(ds[k], id(k, y), a);
      k >>= 1;
    }
  }

  S prod(K l, K d, K r, K u) {
    int a = id(l), b = id(r);
    a += n;
    b += n;
    S L = m.e(), R = m.e();
    while (a < b) {
      if (a & 1) {
        L = m.op(L, m.prod(ds[a], id(a, d), id(a, u)));
        ++a;
      }
      if (b & 1) {
        --b;
        R = m.op(m.prod(ds[b], id(b, d), id(b, u)), R);
      }
      a >>= 1;
      b >>= 1;
    }
    return m.op(L, R);
  }
};

Back to top page