rectangle_affine_kd_tree.hpp¶
在二维点集上对矩形内点权施加仿射变换并查询矩形和；适合动态二维范围更新。
Complexity: Time: Expected O(n log n) build, O(log n) point assignment, and O(sqrt(n)) per rectangle sum or affine update; rectangle operations are O(n) in the worst case. Space: O(n).
AC 记录：dynamic_point_set_rectangle_affine_rectangle_sum。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: Expected O(n log n) build, O(log n) point assignment,
/// and O(sqrt(n)) per rectangle sum or affine update; rectangle operations are
/// O(n) in the worst case. Space: O(n).
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline dynamic weighted point set using a balanced two-dimensional
/// KD-tree. Every node stores its coordinate bounding box, active-point count,
/// weight sum, and a lazy affine tag. A rectangle operation stops at a fully
/// covered box, while points that will be inserted later start inactive, so
/// earlier affine updates neither count nor change them.
template <class Coordinate, class Value> class rectangle_affine_kd_tree {
public:
using point_type = std::pair<Coordinate, Coordinate>;
rectangle_affine_kd_tree() = default;
rectangle_affine_kd_tree(const std::vector<point_type> &pt,
const std::vector<Value> &arr,
const std::vector<bool> &on) {
build(pt, arr, on);
}
/// @brief Build from every coordinate that can ever be inserted. Inactive
/// points ignore rectangle operations until point_set activates them.
void build(const std::vector<point_type> &pt, const std::vector<Value> &arr,
const std::vector<bool> &on) {
assert(pt.size() == arr.size());
assert(pt.size() == on.size());
pt0 = pt;
rk.assign(pt.size(), 0);
tr.assign(std::max<std::size_t>(1, pt.size() * 4), node{});
std::vector<int> ord(pt.size());
std::iota(ord.begin(), ord.end(), 0);
if (!ord.empty()) {
build_at(1, 0, int(ord.size()), 0, ord, arr, on);
}
}
/// @brief Return the number of offline coordinate instances.
int size() const { return int(pt0.size()); }
/// @brief Assign one point's weight and mark it active.
void point_set(int idx, const Value &val) {
assert(0 <= idx && idx < size());
point_set_at(1, 0, size(), rk[idx], val);
}
/// @brief Sum active weights in [l, r) x [dn, top).
Value rectangle_sum(const Coordinate &l, const Coordinate &r,
const Coordinate &dn, const Coordinate &top) {
if (size() == 0 || !(l < r) || !(dn < top)) {
return Value(0);
}
return rectangle_sum_at(1, 0, size(), l, r, dn, top);
}
/// @brief Replace every active weight w in the half-open rectangle by
/// multiplier * w + addend.
void rectangle_apply(const Coordinate &l, const Coordinate &r,
const Coordinate &dn, const Coordinate &top,
const Value &k, const Value &B) {
if (size() == 0 || !(l < r) || !(dn < top)) {
return;
}
rectangle_apply_at(1, 0, size(), l, r, dn, top, k, B);
}
private:
struct node {
Coordinate xl{};
Coordinate xr{};
Coordinate yl{};
Coordinate yr{};
Value sum = Value(0);
int cnt = 0;
Value mul = Value(1);
Value add = Value(0);
bool tag = false;
};
std::vector<point_type> pt0;
std::vector<int> rk;
std::vector<node> tr;
void build_at(int id, int l, int r, int dim, std::vector<int> &ord,
const std::vector<Value> &arr, const std::vector<bool> &on) {
if (l + 1 == r) {
int idx = ord[l];
rk[idx] = l;
const auto &[x, y] = pt0[idx];
tr[id].xl = tr[id].xr = x;
tr[id].yl = tr[id].yr = y;
tr[id].cnt = on[idx] ? 1 : 0;
tr[id].sum = on[idx] ? arr[idx] : Value(0);
return;
}
int mid = (l + r) / 2;
auto cmp = [&](int A, int rhs) {
const auto &a = pt0[A];
const auto &b = pt0[rhs];
if (dim == 0) {
if (a.first != b.first) {
return a.first < b.first;
}
if (a.second != b.second) {
return a.second < b.second;
}
} else {
if (a.second != b.second) {
return a.second < b.second;
}
if (a.first != b.first) {
return a.first < b.first;
}
}
return A < rhs;
};
std::nth_element(ord.begin() + l, ord.begin() + mid, ord.begin() + r, cmp);
build_at(id * 2, l, mid, dim ^ 1, ord, arr, on);
build_at(id * 2 + 1, mid, r, dim ^ 1, ord, arr, on);
pull(id);
}
void pull(int id) {
const node &A = tr[id * 2];
const node &rhs = tr[id * 2 + 1];
tr[id].xl = std::min(A.xl, rhs.xl);
tr[id].xr = std::max(A.xr, rhs.xr);
tr[id].yl = std::min(A.yl, rhs.yl);
tr[id].yr = std::max(A.yr, rhs.yr);
tr[id].sum = A.sum + rhs.sum;
tr[id].cnt = A.cnt + rhs.cnt;
}
void apply_node(int id, const Value &k, const Value &B) {
node &cur = tr[id];
cur.sum = k * cur.sum + B * Value(cur.cnt);
if (cur.tag) {
cur.mul = k * cur.mul;
cur.add = k * cur.add + B;
} else {
cur.mul = k;
cur.add = B;
cur.tag = true;
}
}
void push(int id) {
node &cur = tr[id];
if (!cur.tag) {
return;
}
apply_node(id * 2, cur.mul, cur.add);
apply_node(id * 2 + 1, cur.mul, cur.add);
cur.mul = Value(1);
cur.add = Value(0);
cur.tag = false;
}
static bool disjoint(const node &cur, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top) {
return cur.xr < l || !(cur.xl < r) || cur.yr < dn || !(cur.yl < top);
}
static bool contained(const node &cur, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top) {
return !(cur.xl < l) && cur.xr < r && !(cur.yl < dn) && cur.yr < top;
}
void point_set_at(int id, int l, int r, int pos, const Value &val) {
if (l + 1 == r) {
tr[id].sum = val;
tr[id].cnt = 1;
tr[id].mul = Value(1);
tr[id].add = Value(0);
tr[id].tag = false;
return;
}
push(id);
int mid = (l + r) / 2;
if (pos < mid) {
point_set_at(id * 2, l, mid, pos, val);
} else {
point_set_at(id * 2 + 1, mid, r, pos, val);
}
pull(id);
}
Value rectangle_sum_at(int id, int il, int ir, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top) {
const node &cur = tr[id];
if (disjoint(cur, l, r, dn, top)) {
return Value(0);
}
if (contained(cur, l, r, dn, top)) {
return cur.sum;
}
push(id);
int mid = (il + ir) / 2;
return rectangle_sum_at(id * 2, il, mid, l, r, dn, top) +
rectangle_sum_at(id * 2 + 1, mid, ir, l, r, dn, top);
}
void rectangle_apply_at(int id, int il, int ir, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top, const Value &k,
const Value &B) {
const node &cur = tr[id];
if (disjoint(cur, l, r, dn, top)) {
return;
}
if (contained(cur, l, r, dn, top)) {
apply_node(id, k, B);
return;
}
push(id);
int mid = (il + ir) / 2;
rectangle_apply_at(id * 2, il, mid, l, r, dn, top, k, B);
rectangle_apply_at(id * 2 + 1, mid, ir, l, r, dn, top, k, B);
pull(id);
}
};
} // namespace noya
#ifndef NOYA_RECTANGLE_AFFINE_KD_TREE_HPP
#define NOYA_RECTANGLE_AFFINE_KD_TREE_HPP 1
/// @complexity Time: Expected O(n log n) build, O(log n) point assignment,
/// and O(sqrt(n)) per rectangle sum or affine update; rectangle operations are
/// O(n) in the worst case. Space: O(n).
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline dynamic weighted point set using a balanced two-dimensional
/// KD-tree. Every node stores its coordinate bounding box, active-point count,
/// weight sum, and a lazy affine tag. A rectangle operation stops at a fully
/// covered box, while points that will be inserted later start inactive, so
/// earlier affine updates neither count nor change them.
template <class Coordinate, class Value> class rectangle_affine_kd_tree {
public:
using point_type = std::pair<Coordinate, Coordinate>;
rectangle_affine_kd_tree() = default;
rectangle_affine_kd_tree(const std::vector<point_type> &pt,
const std::vector<Value> &arr,
const std::vector<bool> &on) {
build(pt, arr, on);
}
/// @brief Build from every coordinate that can ever be inserted. Inactive
/// points ignore rectangle operations until point_set activates them.
void build(const std::vector<point_type> &pt, const std::vector<Value> &arr,
const std::vector<bool> &on) {
assert(pt.size() == arr.size());
assert(pt.size() == on.size());
pt0 = pt;
rk.assign(pt.size(), 0);
tr.assign(std::max<std::size_t>(1, pt.size() * 4), node{});
std::vector<int> ord(pt.size());
std::iota(ord.begin(), ord.end(), 0);
if (!ord.empty()) {
build_at(1, 0, int(ord.size()), 0, ord, arr, on);
}
}
/// @brief Return the number of offline coordinate instances.
int size() const { return int(pt0.size()); }
/// @brief Assign one point's weight and mark it active.
void point_set(int idx, const Value &val) {
assert(0 <= idx && idx < size());
point_set_at(1, 0, size(), rk[idx], val);
}
/// @brief Sum active weights in [l, r) x [dn, top).
Value rectangle_sum(const Coordinate &l, const Coordinate &r,
const Coordinate &dn, const Coordinate &top) {
if (size() == 0 || !(l < r) || !(dn < top)) {
return Value(0);
}
return rectangle_sum_at(1, 0, size(), l, r, dn, top);
}
/// @brief Replace every active weight w in the half-open rectangle by
/// multiplier * w + addend.
void rectangle_apply(const Coordinate &l, const Coordinate &r,
const Coordinate &dn, const Coordinate &top,
const Value &k, const Value &B) {
if (size() == 0 || !(l < r) || !(dn < top)) {
return;
}
rectangle_apply_at(1, 0, size(), l, r, dn, top, k, B);
}
private:
struct node {
Coordinate xl{};
Coordinate xr{};
Coordinate yl{};
Coordinate yr{};
Value sum = Value(0);
int cnt = 0;
Value mul = Value(1);
Value add = Value(0);
bool tag = false;
};
std::vector<point_type> pt0;
std::vector<int> rk;
std::vector<node> tr;
void build_at(int id, int l, int r, int dim, std::vector<int> &ord,
const std::vector<Value> &arr, const std::vector<bool> &on) {
if (l + 1 == r) {
int idx = ord[l];
rk[idx] = l;
const auto &[x, y] = pt0[idx];
tr[id].xl = tr[id].xr = x;
tr[id].yl = tr[id].yr = y;
tr[id].cnt = on[idx] ? 1 : 0;
tr[id].sum = on[idx] ? arr[idx] : Value(0);
return;
}
int mid = (l + r) / 2;
auto cmp = [&](int A, int rhs) {
const auto &a = pt0[A];
const auto &b = pt0[rhs];
if (dim == 0) {
if (a.first != b.first) {
return a.first < b.first;
}
if (a.second != b.second) {
return a.second < b.second;
}
} else {
if (a.second != b.second) {
return a.second < b.second;
}
if (a.first != b.first) {
return a.first < b.first;
}
}
return A < rhs;
};
std::nth_element(ord.begin() + l, ord.begin() + mid, ord.begin() + r, cmp);
build_at(id * 2, l, mid, dim ^ 1, ord, arr, on);
build_at(id * 2 + 1, mid, r, dim ^ 1, ord, arr, on);
pull(id);
}
void pull(int id) {
const node &A = tr[id * 2];
const node &rhs = tr[id * 2 + 1];
tr[id].xl = std::min(A.xl, rhs.xl);
tr[id].xr = std::max(A.xr, rhs.xr);
tr[id].yl = std::min(A.yl, rhs.yl);
tr[id].yr = std::max(A.yr, rhs.yr);
tr[id].sum = A.sum + rhs.sum;
tr[id].cnt = A.cnt + rhs.cnt;
}
void apply_node(int id, const Value &k, const Value &B) {
node &cur = tr[id];
cur.sum = k * cur.sum + B * Value(cur.cnt);
if (cur.tag) {
cur.mul = k * cur.mul;
cur.add = k * cur.add + B;
} else {
cur.mul = k;
cur.add = B;
cur.tag = true;
}
}
void push(int id) {
node &cur = tr[id];
if (!cur.tag) {
return;
}
apply_node(id * 2, cur.mul, cur.add);
apply_node(id * 2 + 1, cur.mul, cur.add);
cur.mul = Value(1);
cur.add = Value(0);
cur.tag = false;
}
static bool disjoint(const node &cur, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top) {
return cur.xr < l || !(cur.xl < r) || cur.yr < dn || !(cur.yl < top);
}
static bool contained(const node &cur, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top) {
return !(cur.xl < l) && cur.xr < r && !(cur.yl < dn) && cur.yr < top;
}
void point_set_at(int id, int l, int r, int pos, const Value &val) {
if (l + 1 == r) {
tr[id].sum = val;
tr[id].cnt = 1;
tr[id].mul = Value(1);
tr[id].add = Value(0);
tr[id].tag = false;
return;
}
push(id);
int mid = (l + r) / 2;
if (pos < mid) {
point_set_at(id * 2, l, mid, pos, val);
} else {
point_set_at(id * 2 + 1, mid, r, pos, val);
}
pull(id);
}
Value rectangle_sum_at(int id, int il, int ir, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top) {
const node &cur = tr[id];
if (disjoint(cur, l, r, dn, top)) {
return Value(0);
}
if (contained(cur, l, r, dn, top)) {
return cur.sum;
}
push(id);
int mid = (il + ir) / 2;
return rectangle_sum_at(id * 2, il, mid, l, r, dn, top) +
rectangle_sum_at(id * 2 + 1, mid, ir, l, r, dn, top);
}
void rectangle_apply_at(int id, int il, int ir, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top, const Value &k,
const Value &B) {
const node &cur = tr[id];
if (disjoint(cur, l, r, dn, top)) {
return;
}
if (contained(cur, l, r, dn, top)) {
apply_node(id, k, B);
return;
}
push(id);
int mid = (il + ir) / 2;
rectangle_apply_at(id * 2, il, mid, l, r, dn, top, k, B);
rectangle_apply_at(id * 2 + 1, mid, ir, l, r, dn, top, k, B);
pull(id);
}
};
} // namespace noya
#endif // NOYA_RECTANGLE_AFFINE_KD_TREE_HPP
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>
/// @complexity Time: Expected O(n log n) build, O(log n) point assignment,
/// and O(sqrt(n)) per rectangle sum or affine update; rectangle operations are
/// O(n) in the worst case. Space: O(n).
namespace noya {
/// @brief Offline dynamic weighted point set using a balanced two-dimensional
/// KD-tree. Every node stores its coordinate bounding box, active-point count,
/// weight sum, and a lazy affine tag. A rectangle operation stops at a fully
/// covered box, while points that will be inserted later start inactive, so
/// earlier affine updates neither count nor change them.
template <class Coordinate, class Value> class rectangle_affine_kd_tree {
public:
using point_type = std::pair<Coordinate, Coordinate>;
rectangle_affine_kd_tree() = default;
rectangle_affine_kd_tree(const std::vector<point_type> &pt,
const std::vector<Value> &arr,
const std::vector<bool> &on) {
build(pt, arr, on);
}
/// @brief Build from every coordinate that can ever be inserted. Inactive
/// points ignore rectangle operations until point_set activates them.
void build(const std::vector<point_type> &pt, const std::vector<Value> &arr,
const std::vector<bool> &on) {
assert(pt.size() == arr.size());
assert(pt.size() == on.size());
pt0 = pt;
rk.assign(pt.size(), 0);
tr.assign(std::max<std::size_t>(1, pt.size() * 4), node{});
std::vector<int> ord(pt.size());
std::iota(ord.begin(), ord.end(), 0);
if (!ord.empty()) {
build_at(1, 0, int(ord.size()), 0, ord, arr, on);
}
}
/// @brief Return the number of offline coordinate instances.
int size() const { return int(pt0.size()); }
/// @brief Assign one point's weight and mark it active.
void point_set(int idx, const Value &val) {
assert(0 <= idx && idx < size());
point_set_at(1, 0, size(), rk[idx], val);
}
/// @brief Sum active weights in [l, r) x [dn, top).
Value rectangle_sum(const Coordinate &l, const Coordinate &r,
const Coordinate &dn, const Coordinate &top) {
if (size() == 0 || !(l < r) || !(dn < top)) {
return Value(0);
}
return rectangle_sum_at(1, 0, size(), l, r, dn, top);
}
/// @brief Replace every active weight w in the half-open rectangle by
/// multiplier * w + addend.
void rectangle_apply(const Coordinate &l, const Coordinate &r,
const Coordinate &dn, const Coordinate &top,
const Value &k, const Value &B) {
if (size() == 0 || !(l < r) || !(dn < top)) {
return;
}
rectangle_apply_at(1, 0, size(), l, r, dn, top, k, B);
}
private:
struct node {
Coordinate xl{};
Coordinate xr{};
Coordinate yl{};
Coordinate yr{};
Value sum = Value(0);
int cnt = 0;
Value mul = Value(1);
Value add = Value(0);
bool tag = false;
};
std::vector<point_type> pt0;
std::vector<int> rk;
std::vector<node> tr;
void build_at(int id, int l, int r, int dim, std::vector<int> &ord,
const std::vector<Value> &arr, const std::vector<bool> &on) {
if (l + 1 == r) {
int idx = ord[l];
rk[idx] = l;
const auto &[x, y] = pt0[idx];
tr[id].xl = tr[id].xr = x;
tr[id].yl = tr[id].yr = y;
tr[id].cnt = on[idx] ? 1 : 0;
tr[id].sum = on[idx] ? arr[idx] : Value(0);
return;
}
int mid = (l + r) / 2;
auto cmp = [&](int A, int rhs) {
const auto &a = pt0[A];
const auto &b = pt0[rhs];
if (dim == 0) {
if (a.first != b.first) {
return a.first < b.first;
}
if (a.second != b.second) {
return a.second < b.second;
}
} else {
if (a.second != b.second) {
return a.second < b.second;
}
if (a.first != b.first) {
return a.first < b.first;
}
}
return A < rhs;
};
std::nth_element(ord.begin() + l, ord.begin() + mid, ord.begin() + r, cmp);
build_at(id * 2, l, mid, dim ^ 1, ord, arr, on);
build_at(id * 2 + 1, mid, r, dim ^ 1, ord, arr, on);
pull(id);
}
void pull(int id) {
const node &A = tr[id * 2];
const node &rhs = tr[id * 2 + 1];
tr[id].xl = std::min(A.xl, rhs.xl);
tr[id].xr = std::max(A.xr, rhs.xr);
tr[id].yl = std::min(A.yl, rhs.yl);
tr[id].yr = std::max(A.yr, rhs.yr);
tr[id].sum = A.sum + rhs.sum;
tr[id].cnt = A.cnt + rhs.cnt;
}
void apply_node(int id, const Value &k, const Value &B) {
node &cur = tr[id];
cur.sum = k * cur.sum + B * Value(cur.cnt);
if (cur.tag) {
cur.mul = k * cur.mul;
cur.add = k * cur.add + B;
} else {
cur.mul = k;
cur.add = B;
cur.tag = true;
}
}
void push(int id) {
node &cur = tr[id];
if (!cur.tag) {
return;
}
apply_node(id * 2, cur.mul, cur.add);
apply_node(id * 2 + 1, cur.mul, cur.add);
cur.mul = Value(1);
cur.add = Value(0);
cur.tag = false;
}
static bool disjoint(const node &cur, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top) {
return cur.xr < l || !(cur.xl < r) || cur.yr < dn || !(cur.yl < top);
}
static bool contained(const node &cur, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top) {
return !(cur.xl < l) && cur.xr < r && !(cur.yl < dn) && cur.yr < top;
}
void point_set_at(int id, int l, int r, int pos, const Value &val) {
if (l + 1 == r) {
tr[id].sum = val;
tr[id].cnt = 1;
tr[id].mul = Value(1);
tr[id].add = Value(0);
tr[id].tag = false;
return;
}
push(id);
int mid = (l + r) / 2;
if (pos < mid) {
point_set_at(id * 2, l, mid, pos, val);
} else {
point_set_at(id * 2 + 1, mid, r, pos, val);
}
pull(id);
}
Value rectangle_sum_at(int id, int il, int ir, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top) {
const node &cur = tr[id];
if (disjoint(cur, l, r, dn, top)) {
return Value(0);
}
if (contained(cur, l, r, dn, top)) {
return cur.sum;
}
push(id);
int mid = (il + ir) / 2;
return rectangle_sum_at(id * 2, il, mid, l, r, dn, top) +
rectangle_sum_at(id * 2 + 1, mid, ir, l, r, dn, top);
}
void rectangle_apply_at(int id, int il, int ir, const Coordinate &l,
const Coordinate &r, const Coordinate &dn,
const Coordinate &top, const Value &k,
const Value &B) {
const node &cur = tr[id];
if (disjoint(cur, l, r, dn, top)) {
return;
}
if (contained(cur, l, r, dn, top)) {
apply_node(id, k, B);
return;
}
push(id);
int mid = (il + ir) / 2;
rectangle_apply_at(id * 2, il, mid, l, r, dn, top, k, B);
rectangle_apply_at(id * 2 + 1, mid, ir, l, r, dn, top, k, B);
pull(id);
}
};
} // namespace noya