領域木(Segment Tree)
(data-structure-2d/segment-tree-on-range-tree.hpp)

• View this file on GitHub
• Last update: 2021-12-30 19:20:16+09:00
• Include: #include "data-structure-2d/segment-tree-on-range-tree.hpp"

Depends on

• segment-tree/segment-tree.hpp

Verified with

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

Code

#pragma once



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

// S ... index_type
// T ... value_type
// F ... function_type
template <typename S, typename T, typename F>
struct RangeTree {
  using Seg = SegmentTree<T, F>;
  using P = pair<S, S>;

  S N, M;
  const F f;
  T ti;
  vector<SegmentTree<T, F>> seg;
  vector<vector<S>> ys;
  vector<P> ps;

  RangeTree(const F& f_, const T& ti_) : f(f_), ti(ti_) {}

  void add_point(S x, S y) { ps.push_back(make_pair(x, y)); }

  void build() {
    sort(begin(ps), end(ps));
    ps.erase(unique(begin(ps), end(ps)), end(ps));
    N = ps.size();
    for (int i = 0; i < 2 * N; ++i) seg.push_back(Seg{f, ti});
    ys.resize(2 * N);
    for (int i = 0; i < N; ++i) {
      ys[i + N].push_back(ps[i].second);
      seg[i + N].init(1);
    }
    for (int i = N - 1; i > 0; --i) {
      ys[i].resize(ys[i << 1].size() + ys[(i << 1) | 1].size());
      merge(begin(ys[(i << 1) | 0]), end(ys[(i << 1) | 0]),
            begin(ys[(i << 1) | 1]), end(ys[(i << 1) | 1]), begin(ys[i]));
      ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
      seg[i].init(ys[i].size());
    }
  }

  int id(S x) const {
    return lower_bound(
               begin(ps), end(ps), make_pair(x, S()),
               [](const P& a, const P& b) { return a.first < b.first; }) -
           begin(ps);
  }

  int id(int i, S y) const {
    return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
  }

  void add(S x, S y, T a) {
    int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
    assert(ps[i] == make_pair(x, y));
    for (i += N; i; i >>= 1) seg[i].add(id(i, y), a);
  }

  T sum(S xl, S yl, S xr, S yr) {
    T L = ti, R = ti;
    int a = id(xl), b = id(xr);
    for (a += N, b += N; a < b; a >>= 1, b >>= 1) {
      if (a & 1) L = f(L, seg[a].query(id(a, yl), id(a, yr))), ++a;
      if (b & 1) --b, R = f(seg[b].query(id(b, yl), id(b, yr)), R);
    }
    return f(L, R);
  }
};

/*
 * @brief 領域木(Segment Tree)
 */

#line 2 "data-structure-2d/segment-tree-on-range-tree.hpp"



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

template <typename T, typename F>
struct SegmentTree {
  int N;
  int size;
  vector<T> seg;
  const F f;
  const T I;

  SegmentTree(F _f, const T &I_) : N(0), size(0), f(_f), I(I_) {}

  SegmentTree(int _N, F _f, const T &I_) : f(_f), I(I_) { init(_N); }

  SegmentTree(const vector<T> &v, F _f, T I_) : f(_f), I(I_) {
    init(v.size());
    for (int i = 0; i < (int)v.size(); i++) {
      seg[i + size] = v[i];
    }
    build();
  }

  void init(int _N) {
    N = _N;
    size = 1;
    while (size < N) size <<= 1;
    seg.assign(2 * size, I);
  }

  void set(int k, T x) { seg[k + size] = x; }

  void build() {
    for (int k = size - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k], seg[2 * k + 1]);
    }
  }

  void update(int k, T x) {
    k += size;
    seg[k] = x;
    while (k >>= 1) {
      seg[k] = f(seg[2 * k], seg[2 * k + 1]);
    }
  }

  void add(int k, T x) {
    k += size;
    seg[k] += x;
    while (k >>= 1) {
      seg[k] = f(seg[2 * k], seg[2 * k + 1]);
    }
  }

  // query to [a, b)
  T query(int a, int b) {
    T L = I, R = I;
    for (a += size, b += size; a < b; a >>= 1, b >>= 1) {
      if (a & 1) L = f(L, seg[a++]);
      if (b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  T &operator[](const int &k) { return seg[k + size]; }

  // check(a[l] * ...  * a[r-1]) が true となる最大の r
  // (右端まですべて true なら N を返す)
  template <class C>
  int max_right(int l, C check) {
    assert(0 <= l && l <= N);
    assert(check(I) == true);
    if (l == N) return N;
    l += size;
    T sm = I;
    do {
      while (l % 2 == 0) l >>= 1;
      if (!check(f(sm, seg[l]))) {
        while (l < size) {
          l = (2 * l);
          if (check(f(sm, seg[l]))) {
            sm = f(sm, seg[l]);
            l++;
          }
        }
        return l - size;
      }
      sm = f(sm, seg[l]);
      l++;
    } while ((l & -l) != l);
    return N;
  }

  // check(a[l] * ... * a[r-1]) が true となる最小の l
  // (左端まで true なら 0 を返す)
  template <typename C>
  int min_left(int r, C check) {
    assert(0 <= r && r <= N);
    assert(check(I) == true);
    if (r == 0) return 0;
    r += size;
    T sm = I;
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!check(f(seg[r], sm))) {
        while (r < size) {
          r = (2 * r + 1);
          if (check(f(seg[r], sm))) {
            sm = f(seg[r], sm);
            r--;
          }
        }
        return r + 1 - size;
      }
      sm = f(seg[r], sm);
    } while ((r & -r) != r);
    return 0;
  }
};
#line 6 "data-structure-2d/segment-tree-on-range-tree.hpp"

// S ... index_type
// T ... value_type
// F ... function_type
template <typename S, typename T, typename F>
struct RangeTree {
  using Seg = SegmentTree<T, F>;
  using P = pair<S, S>;

  S N, M;
  const F f;
  T ti;
  vector<SegmentTree<T, F>> seg;
  vector<vector<S>> ys;
  vector<P> ps;

  RangeTree(const F& f_, const T& ti_) : f(f_), ti(ti_) {}

  void add_point(S x, S y) { ps.push_back(make_pair(x, y)); }

  void build() {
    sort(begin(ps), end(ps));
    ps.erase(unique(begin(ps), end(ps)), end(ps));
    N = ps.size();
    for (int i = 0; i < 2 * N; ++i) seg.push_back(Seg{f, ti});
    ys.resize(2 * N);
    for (int i = 0; i < N; ++i) {
      ys[i + N].push_back(ps[i].second);
      seg[i + N].init(1);
    }
    for (int i = N - 1; i > 0; --i) {
      ys[i].resize(ys[i << 1].size() + ys[(i << 1) | 1].size());
      merge(begin(ys[(i << 1) | 0]), end(ys[(i << 1) | 0]),
            begin(ys[(i << 1) | 1]), end(ys[(i << 1) | 1]), begin(ys[i]));
      ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
      seg[i].init(ys[i].size());
    }
  }

  int id(S x) const {
    return lower_bound(
               begin(ps), end(ps), make_pair(x, S()),
               [](const P& a, const P& b) { return a.first < b.first; }) -
           begin(ps);
  }

  int id(int i, S y) const {
    return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
  }

  void add(S x, S y, T a) {
    int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
    assert(ps[i] == make_pair(x, y));
    for (i += N; i; i >>= 1) seg[i].add(id(i, y), a);
  }

  T sum(S xl, S yl, S xr, S yr) {
    T L = ti, R = ti;
    int a = id(xl), b = id(xr);
    for (a += N, b += N; a < b; a >>= 1, b >>= 1) {
      if (a & 1) L = f(L, seg[a].query(id(a, yl), id(a, yr))), ++a;
      if (b & 1) --b, R = f(seg[b].query(id(b, yl), id(b, yr)), R);
    }
    return f(L, R);
  }
};

/*
 * @brief 領域木(Segment Tree)
 */

Back to top page