抽象化領域木
(data-structure-2d/abstract-range-tree.hpp)

• View this file on GitHub
• Last update: 2026-06-27 14:52:13+09:00
• Include: #include "data-structure-2d/abstract-range-tree.hpp"

Depends on

• internal/internal-function.hpp

Verified with

• verify/verify-yosupo-ds/yosupo-point-add-rectangle-sum-abstract-range-tree.test.cpp

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <functional>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;

#include "../internal/internal-function.hpp"

// DS ... data_structure_type
// S ... size_type
// T ... value_type
template <typename DS, typename S, typename T,
          typename NewFunc = nyaan_internal::inplace_function<DS*(int), 64>,
          typename AddFunc = nyaan_internal::inplace_function<void(DS&, int, T), 64>,
          typename SumFunc = nyaan_internal::inplace_function<T(DS&, int, int), 64>,
          typename MergeFunc = nyaan_internal::inplace_function<T(T, T), 64>>
struct RangeTree {
  using NEW = NewFunc;
  using ADD = AddFunc;
  using SUM = SumFunc;
  using MRG = MergeFunc;
  using P = pair<S, S>;

  static_assert(is_invocable_r_v<DS*, NEW&, int>,
                "RangeTree NEW must be callable as DS*(int)");
  static_assert(is_invocable_r_v<void, ADD&, DS&, int, T>,
                "RangeTree ADD must be callable as void(DS&, int, T)");
  static_assert(is_invocable_r_v<T, SUM&, DS&, int, int>,
                "RangeTree SUM must be callable as T(DS&, int, int)");
  static_assert(is_invocable_r_v<T, MRG&, T, T>,
                "RangeTree MRG must be callable as T(T, T)");

  S N, M;
  NEW ds_new;
  ADD ds_add;
  SUM ds_sum;
  MRG t_merge;
  const T ti;
  vector<DS*> ds;
  vector<vector<S>> ys;
  vector<P> ps;

  template <typename FNew, typename FAdd, typename FSum, typename FMerge>
  RangeTree(FNew&& nw, FAdd&& ad, FSum&& sm, FMerge&& mrg, const T& ti_)
      : ds_new(std::forward<FNew>(nw)),
        ds_add(std::forward<FAdd>(ad)),
        ds_sum(std::forward<FSum>(sm)),
        t_merge(std::forward<FMerge>(mrg)),
        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();
    ds.resize(2 * N, nullptr);
    ys.resize(2 * N);
    for (int i = 0; i < N; ++i) {
      ys[i + N].push_back(ps[i].second);
      ds[i + N] = std::invoke(ds_new, 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]));
      ds[i] = std::invoke(ds_new, 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) std::invoke(ds_add, *ds[i], 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 = std::invoke(t_merge, L,
                        std::invoke(ds_sum, *ds[a], id(a, yl), id(a, yr))),
        ++a;
      if (b & 1)
        --b,
            R = std::invoke(t_merge,
                            std::invoke(ds_sum, *ds[b], id(b, yl), id(b, yr)),
                            R);
    }
    return std::invoke(t_merge, L, R);
  }
};

/*
 * @brief 抽象化領域木
 */

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

#include <algorithm>
#include <cassert>
#include <functional>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;

#line 2 "internal/internal-function.hpp"

#include <cstddef>
#line 5 "internal/internal-function.hpp"
#include <memory>
#line 8 "internal/internal-function.hpp"

namespace nyaan_internal {

template <class>
class function_ref;

template <class R, class... Args>
class function_ref<R(Args...)> {
  void* obj_ = nullptr;
  R (*call_obj_)(void*, Args...) = nullptr;
  R (*func_)(Args...) = nullptr;

 public:
  function_ref() noexcept = default;
  function_ref(std::nullptr_t) noexcept {}
  function_ref(R (*f)(Args...)) noexcept : func_(f) {}

  template <
      class F, class Fn = std::remove_reference_t<F>,
      class = std::enable_if_t<
          std::is_lvalue_reference_v<F&&> &&
          !std::is_same_v<std::decay_t<F>, function_ref> &&
          !std::is_pointer_v<std::decay_t<F>> && !std::is_function_v<Fn> &&
          std::is_invocable_r_v<R, Fn&, Args...>>>
  function_ref(F&& f) noexcept {
    obj_ = const_cast<void*>(static_cast<const void*>(std::addressof(f)));
    call_obj_ = [](void* p, Args... args) -> R {
      return std::invoke(*static_cast<Fn*>(p), std::forward<Args>(args)...);
    };
  }

  R operator()(Args... args) const {
    if (call_obj_) {
      return call_obj_(obj_, std::forward<Args>(args)...);
    }
    if (!func_) throw std::bad_function_call();
    return func_(std::forward<Args>(args)...);
  }

  explicit operator bool() const noexcept {
    return call_obj_ != nullptr || func_ != nullptr;
  }
};

template <class, std::size_t Capacity = 32,
          std::size_t Align = alignof(std::max_align_t)>
class inplace_function;

template <class R, class... Args, std::size_t Capacity, std::size_t Align>
class inplace_function<R(Args...), Capacity, Align> {
  using storage_t = typename std::aligned_storage<Capacity, Align>::type;

  storage_t storage_;
  R (*invoke_)(void*, Args&&...) = nullptr;
  void (*copy_)(void*, const void*) = nullptr;
  void (*move_)(void*, void*) = nullptr;
  void (*destroy_)(void*) = nullptr;

  template <class F>
  static R invoke_impl(void* p, Args&&... args) {
    return std::invoke(*static_cast<F*>(p), std::forward<Args>(args)...);
  }

  template <class F>
  static void copy_impl(void* dst, const void* src) {
    new (dst) F(*static_cast<const F*>(src));
  }

  template <class F>
  static void move_impl(void* dst, void* src) {
    if constexpr (std::is_move_constructible_v<F>) {
      new (dst) F(std::move(*static_cast<F*>(src)));
    } else {
      new (dst) F(*static_cast<F*>(src));
    }
  }

  template <class F>
  static void destroy_impl(void* p) {
    static_cast<F*>(p)->~F();
  }

  template <class F>
  void emplace(F&& f) {
    using Fn = std::decay_t<F>;

    static_assert(std::is_invocable_r_v<R, Fn&, Args...>,
                  "inplace_function target is not invocable with this signature");
    static_assert(sizeof(Fn) <= Capacity,
                  "inplace_function target is too large; increase Capacity");
    static_assert(alignof(Fn) <= Align,
                  "inplace_function target alignment is too strict; increase Align");
    static_assert(std::is_copy_constructible_v<Fn>,
                  "inplace_function target must be copy constructible");

    if constexpr (std::is_pointer_v<Fn>) {
      if (f == nullptr) return;
    }

    if constexpr (std::is_move_constructible_v<Fn> ||
                  std::is_lvalue_reference_v<F>) {
      new (&storage_) Fn(std::forward<F>(f));
    } else {
      new (&storage_) Fn(f);
    }
    invoke_ = &invoke_impl<Fn>;
    copy_ = &copy_impl<Fn>;
    move_ = &move_impl<Fn>;
    destroy_ = &destroy_impl<Fn>;
  }

 public:
  inplace_function() noexcept = default;
  inplace_function(std::nullptr_t) noexcept {}

  ~inplace_function() { reset(); }

  inplace_function(const inplace_function& other) {
    if (other) {
      other.copy_(&storage_, &other.storage_);
      invoke_ = other.invoke_;
      copy_ = other.copy_;
      move_ = other.move_;
      destroy_ = other.destroy_;
    }
  }

  inplace_function(inplace_function&& other) {
    if (other) {
      other.move_(&storage_, &other.storage_);
      invoke_ = other.invoke_;
      copy_ = other.copy_;
      move_ = other.move_;
      destroy_ = other.destroy_;
      other.reset();
    }
  }

  template <
      class F, class Fn = std::decay_t<F>,
      class = std::enable_if_t<!std::is_same_v<Fn, inplace_function> &&
                               !std::is_same_v<Fn, std::nullptr_t>>>
  inplace_function(F&& f) {
    emplace(std::forward<F>(f));
  }

  inplace_function& operator=(const inplace_function& other) {
    if (this == &other) return *this;
    reset();
    if (other) {
      other.copy_(&storage_, &other.storage_);
      invoke_ = other.invoke_;
      copy_ = other.copy_;
      move_ = other.move_;
      destroy_ = other.destroy_;
    }
    return *this;
  }

  inplace_function& operator=(inplace_function&& other) {
    if (this == &other) return *this;
    reset();
    if (other) {
      other.move_(&storage_, &other.storage_);
      invoke_ = other.invoke_;
      copy_ = other.copy_;
      move_ = other.move_;
      destroy_ = other.destroy_;
      other.reset();
    }
    return *this;
  }

  template <
      class F, class Fn = std::decay_t<F>,
      class = std::enable_if_t<!std::is_same_v<Fn, inplace_function> &&
                               !std::is_same_v<Fn, std::nullptr_t>>>
  inplace_function& operator=(F&& f) {
    reset();
    emplace(std::forward<F>(f));
    return *this;
  }

  inplace_function& operator=(std::nullptr_t) noexcept {
    reset();
    return *this;
  }

  void reset() noexcept {
    if (destroy_) destroy_(&storage_);
    invoke_ = nullptr;
    copy_ = nullptr;
    move_ = nullptr;
    destroy_ = nullptr;
  }

  explicit operator bool() const noexcept { return invoke_ != nullptr; }

  R operator()(Args... args) const {
    if (!invoke_) throw std::bad_function_call();
    return invoke_(
        const_cast<void*>(static_cast<const void*>(&storage_)),
        std::forward<Args>(args)...);
  }
};

}  // namespace nyaan_internal

using nyaan_internal::function_ref;
using nyaan_internal::inplace_function;
#line 12 "data-structure-2d/abstract-range-tree.hpp"

// DS ... data_structure_type
// S ... size_type
// T ... value_type
template <typename DS, typename S, typename T,
          typename NewFunc = nyaan_internal::inplace_function<DS*(int), 64>,
          typename AddFunc = nyaan_internal::inplace_function<void(DS&, int, T), 64>,
          typename SumFunc = nyaan_internal::inplace_function<T(DS&, int, int), 64>,
          typename MergeFunc = nyaan_internal::inplace_function<T(T, T), 64>>
struct RangeTree {
  using NEW = NewFunc;
  using ADD = AddFunc;
  using SUM = SumFunc;
  using MRG = MergeFunc;
  using P = pair<S, S>;

  static_assert(is_invocable_r_v<DS*, NEW&, int>,
                "RangeTree NEW must be callable as DS*(int)");
  static_assert(is_invocable_r_v<void, ADD&, DS&, int, T>,
                "RangeTree ADD must be callable as void(DS&, int, T)");
  static_assert(is_invocable_r_v<T, SUM&, DS&, int, int>,
                "RangeTree SUM must be callable as T(DS&, int, int)");
  static_assert(is_invocable_r_v<T, MRG&, T, T>,
                "RangeTree MRG must be callable as T(T, T)");

  S N, M;
  NEW ds_new;
  ADD ds_add;
  SUM ds_sum;
  MRG t_merge;
  const T ti;
  vector<DS*> ds;
  vector<vector<S>> ys;
  vector<P> ps;

  template <typename FNew, typename FAdd, typename FSum, typename FMerge>
  RangeTree(FNew&& nw, FAdd&& ad, FSum&& sm, FMerge&& mrg, const T& ti_)
      : ds_new(std::forward<FNew>(nw)),
        ds_add(std::forward<FAdd>(ad)),
        ds_sum(std::forward<FSum>(sm)),
        t_merge(std::forward<FMerge>(mrg)),
        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();
    ds.resize(2 * N, nullptr);
    ys.resize(2 * N);
    for (int i = 0; i < N; ++i) {
      ys[i + N].push_back(ps[i].second);
      ds[i + N] = std::invoke(ds_new, 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]));
      ds[i] = std::invoke(ds_new, 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) std::invoke(ds_add, *ds[i], 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 = std::invoke(t_merge, L,
                        std::invoke(ds_sum, *ds[a], id(a, yl), id(a, yr))),
        ++a;
      if (b & 1)
        --b,
            R = std::invoke(t_merge,
                            std::invoke(ds_sum, *ds[b], id(b, yl), id(b, yr)),
                            R);
    }
    return std::invoke(t_merge, L, R);
  }
};

/*
 * @brief 抽象化領域木
 */

Back to top page