rectangle_affine_kd_tree.hpp¶
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.
Verified by dynamic_point_set_rectangle_affine_rectangle_sum.
在二维点集上对矩形内点权施加仿射变换并查询矩形和；适合动态二维范围更新。
Implementation¶
#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> &points,
const std::vector<Value> &values,
const std::vector<bool> &active) {
build(points, values, active);
}
/// @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> &points,
const std::vector<Value> &values,
const std::vector<bool> &active) {
assert(points.size() == values.size());
assert(points.size() == active.size());
points_ = points;
rank_.assign(points.size(), 0);
tree_.assign(std::max<std::size_t>(1, points.size() * 4), node{});
std::vector<int> order(points.size());
std::iota(order.begin(), order.end(), 0);
if (!order.empty()) {
build_at(1, 0, int(order.size()), 0, order, values, active);
}
}
/// @brief Return the number of offline coordinate instances.
int size() const { return int(points_.size()); }
/// @brief Assign one point's weight and mark it active.
void point_set(int index, const Value &value) {
assert(0 <= index && index < size());
point_set_at(1, 0, size(), rank_[index], value);
}
/// @brief Sum active weights in [left, right) x [bottom, top).
Value rectangle_sum(const Coordinate &left, const Coordinate &right,
const Coordinate &bottom, const Coordinate &top) {
if (size() == 0 || !(left < right) || !(bottom < top)) {
return Value(0);
}
return rectangle_sum_at(1, 0, size(), left, right, bottom, top);
}
/// @brief Replace every active weight w in the half-open rectangle by
/// multiplier * w + addend.
void rectangle_apply(const Coordinate &left, const Coordinate &right,
const Coordinate &bottom, const Coordinate &top,
const Value &multiplier, const Value &addend) {
if (size() == 0 || !(left < right) || !(bottom < top)) {
return;
}
rectangle_apply_at(1, 0, size(), left, right, bottom, top, multiplier,
addend);
}
private:
struct node {
Coordinate min_x{};
Coordinate max_x{};
Coordinate min_y{};
Coordinate max_y{};
Value sum = Value(0);
int active_count = 0;
Value lazy_multiplier = Value(1);
Value lazy_addend = Value(0);
bool has_lazy = false;
};
std::vector<point_type> points_;
std::vector<int> rank_;
std::vector<node> tree_;
void build_at(int id, int left, int right, int dimension,
std::vector<int> &order, const std::vector<Value> &values,
const std::vector<bool> &active) {
if (left + 1 == right) {
int index = order[left];
rank_[index] = left;
const auto &[x, y] = points_[index];
tree_[id].min_x = tree_[id].max_x = x;
tree_[id].min_y = tree_[id].max_y = y;
tree_[id].active_count = active[index] ? 1 : 0;
tree_[id].sum = active[index] ? values[index] : Value(0);
return;
}
int middle = (left + right) / 2;
auto compare = [&](int first, int second) {
const auto &a = points_[first];
const auto &b = points_[second];
if (dimension == 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 first < second;
};
std::nth_element(order.begin() + left, order.begin() + middle,
order.begin() + right, compare);
build_at(id * 2, left, middle, dimension ^ 1, order, values, active);
build_at(id * 2 + 1, middle, right, dimension ^ 1, order, values, active);
pull(id);
}
void pull(int id) {
const node &first = tree_[id * 2];
const node &second = tree_[id * 2 + 1];
tree_[id].min_x = std::min(first.min_x, second.min_x);
tree_[id].max_x = std::max(first.max_x, second.max_x);
tree_[id].min_y = std::min(first.min_y, second.min_y);
tree_[id].max_y = std::max(first.max_y, second.max_y);
tree_[id].sum = first.sum + second.sum;
tree_[id].active_count = first.active_count + second.active_count;
}
void apply_node(int id, const Value &multiplier, const Value &addend) {
node ¤t = tree_[id];
current.sum = multiplier * current.sum +
addend * Value(current.active_count);
if (current.has_lazy) {
current.lazy_multiplier = multiplier * current.lazy_multiplier;
current.lazy_addend = multiplier * current.lazy_addend + addend;
} else {
current.lazy_multiplier = multiplier;
current.lazy_addend = addend;
current.has_lazy = true;
}
}
void push(int id) {
node ¤t = tree_[id];
if (!current.has_lazy) {
return;
}
apply_node(id * 2, current.lazy_multiplier, current.lazy_addend);
apply_node(id * 2 + 1, current.lazy_multiplier, current.lazy_addend);
current.lazy_multiplier = Value(1);
current.lazy_addend = Value(0);
current.has_lazy = false;
}
static bool disjoint(const node ¤t, const Coordinate &left,
const Coordinate &right, const Coordinate &bottom,
const Coordinate &top) {
return current.max_x < left || !(current.min_x < right) ||
current.max_y < bottom || !(current.min_y < top);
}
static bool contained(const node ¤t, const Coordinate &left,
const Coordinate &right, const Coordinate &bottom,
const Coordinate &top) {
return !(current.min_x < left) && current.max_x < right &&
!(current.min_y < bottom) && current.max_y < top;
}
void point_set_at(int id, int left, int right, int position,
const Value &value) {
if (left + 1 == right) {
tree_[id].sum = value;
tree_[id].active_count = 1;
tree_[id].lazy_multiplier = Value(1);
tree_[id].lazy_addend = Value(0);
tree_[id].has_lazy = false;
return;
}
push(id);
int middle = (left + right) / 2;
if (position < middle) {
point_set_at(id * 2, left, middle, position, value);
} else {
point_set_at(id * 2 + 1, middle, right, position, value);
}
pull(id);
}
Value rectangle_sum_at(int id, int left_index, int right_index,
const Coordinate &left, const Coordinate &right,
const Coordinate &bottom, const Coordinate &top) {
const node ¤t = tree_[id];
if (disjoint(current, left, right, bottom, top)) {
return Value(0);
}
if (contained(current, left, right, bottom, top)) {
return current.sum;
}
push(id);
int middle = (left_index + right_index) / 2;
return rectangle_sum_at(id * 2, left_index, middle, left, right, bottom,
top) +
rectangle_sum_at(id * 2 + 1, middle, right_index, left, right,
bottom, top);
}
void rectangle_apply_at(int id, int left_index, int right_index,
const Coordinate &left, const Coordinate &right,
const Coordinate &bottom, const Coordinate &top,
const Value &multiplier, const Value &addend) {
const node ¤t = tree_[id];
if (disjoint(current, left, right, bottom, top)) {
return;
}
if (contained(current, left, right, bottom, top)) {
apply_node(id, multiplier, addend);
return;
}
push(id);
int middle = (left_index + right_index) / 2;
rectangle_apply_at(id * 2, left_index, middle, left, right, bottom, top,
multiplier, addend);
rectangle_apply_at(id * 2 + 1, middle, right_index, left, right, bottom,
top, multiplier, addend);
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> &points,
const std::vector<Value> &values,
const std::vector<bool> &active) {
build(points, values, active);
}
/// @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> &points,
const std::vector<Value> &values,
const std::vector<bool> &active) {
assert(points.size() == values.size());
assert(points.size() == active.size());
points_ = points;
rank_.assign(points.size(), 0);
tree_.assign(std::max<std::size_t>(1, points.size() * 4), node{});
std::vector<int> order(points.size());
std::iota(order.begin(), order.end(), 0);
if (!order.empty()) {
build_at(1, 0, int(order.size()), 0, order, values, active);
}
}
/// @brief Return the number of offline coordinate instances.
int size() const { return int(points_.size()); }
/// @brief Assign one point's weight and mark it active.
void point_set(int index, const Value &value) {
assert(0 <= index && index < size());
point_set_at(1, 0, size(), rank_[index], value);
}
/// @brief Sum active weights in [left, right) x [bottom, top).
Value rectangle_sum(const Coordinate &left, const Coordinate &right,
const Coordinate &bottom, const Coordinate &top) {
if (size() == 0 || !(left < right) || !(bottom < top)) {
return Value(0);
}
return rectangle_sum_at(1, 0, size(), left, right, bottom, top);
}
/// @brief Replace every active weight w in the half-open rectangle by
/// multiplier * w + addend.
void rectangle_apply(const Coordinate &left, const Coordinate &right,
const Coordinate &bottom, const Coordinate &top,
const Value &multiplier, const Value &addend) {
if (size() == 0 || !(left < right) || !(bottom < top)) {
return;
}
rectangle_apply_at(1, 0, size(), left, right, bottom, top, multiplier,
addend);
}
private:
struct node {
Coordinate min_x{};
Coordinate max_x{};
Coordinate min_y{};
Coordinate max_y{};
Value sum = Value(0);
int active_count = 0;
Value lazy_multiplier = Value(1);
Value lazy_addend = Value(0);
bool has_lazy = false;
};
std::vector<point_type> points_;
std::vector<int> rank_;
std::vector<node> tree_;
void build_at(int id, int left, int right, int dimension,
std::vector<int> &order, const std::vector<Value> &values,
const std::vector<bool> &active) {
if (left + 1 == right) {
int index = order[left];
rank_[index] = left;
const auto &[x, y] = points_[index];
tree_[id].min_x = tree_[id].max_x = x;
tree_[id].min_y = tree_[id].max_y = y;
tree_[id].active_count = active[index] ? 1 : 0;
tree_[id].sum = active[index] ? values[index] : Value(0);
return;
}
int middle = (left + right) / 2;
auto compare = [&](int first, int second) {
const auto &a = points_[first];
const auto &b = points_[second];
if (dimension == 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 first < second;
};
std::nth_element(order.begin() + left, order.begin() + middle,
order.begin() + right, compare);
build_at(id * 2, left, middle, dimension ^ 1, order, values, active);
build_at(id * 2 + 1, middle, right, dimension ^ 1, order, values, active);
pull(id);
}
void pull(int id) {
const node &first = tree_[id * 2];
const node &second = tree_[id * 2 + 1];
tree_[id].min_x = std::min(first.min_x, second.min_x);
tree_[id].max_x = std::max(first.max_x, second.max_x);
tree_[id].min_y = std::min(first.min_y, second.min_y);
tree_[id].max_y = std::max(first.max_y, second.max_y);
tree_[id].sum = first.sum + second.sum;
tree_[id].active_count = first.active_count + second.active_count;
}
void apply_node(int id, const Value &multiplier, const Value &addend) {
node ¤t = tree_[id];
current.sum = multiplier * current.sum +
addend * Value(current.active_count);
if (current.has_lazy) {
current.lazy_multiplier = multiplier * current.lazy_multiplier;
current.lazy_addend = multiplier * current.lazy_addend + addend;
} else {
current.lazy_multiplier = multiplier;
current.lazy_addend = addend;
current.has_lazy = true;
}
}
void push(int id) {
node ¤t = tree_[id];
if (!current.has_lazy) {
return;
}
apply_node(id * 2, current.lazy_multiplier, current.lazy_addend);
apply_node(id * 2 + 1, current.lazy_multiplier, current.lazy_addend);
current.lazy_multiplier = Value(1);
current.lazy_addend = Value(0);
current.has_lazy = false;
}
static bool disjoint(const node ¤t, const Coordinate &left,
const Coordinate &right, const Coordinate &bottom,
const Coordinate &top) {
return current.max_x < left || !(current.min_x < right) ||
current.max_y < bottom || !(current.min_y < top);
}
static bool contained(const node ¤t, const Coordinate &left,
const Coordinate &right, const Coordinate &bottom,
const Coordinate &top) {
return !(current.min_x < left) && current.max_x < right &&
!(current.min_y < bottom) && current.max_y < top;
}
void point_set_at(int id, int left, int right, int position,
const Value &value) {
if (left + 1 == right) {
tree_[id].sum = value;
tree_[id].active_count = 1;
tree_[id].lazy_multiplier = Value(1);
tree_[id].lazy_addend = Value(0);
tree_[id].has_lazy = false;
return;
}
push(id);
int middle = (left + right) / 2;
if (position < middle) {
point_set_at(id * 2, left, middle, position, value);
} else {
point_set_at(id * 2 + 1, middle, right, position, value);
}
pull(id);
}
Value rectangle_sum_at(int id, int left_index, int right_index,
const Coordinate &left, const Coordinate &right,
const Coordinate &bottom, const Coordinate &top) {
const node ¤t = tree_[id];
if (disjoint(current, left, right, bottom, top)) {
return Value(0);
}
if (contained(current, left, right, bottom, top)) {
return current.sum;
}
push(id);
int middle = (left_index + right_index) / 2;
return rectangle_sum_at(id * 2, left_index, middle, left, right, bottom,
top) +
rectangle_sum_at(id * 2 + 1, middle, right_index, left, right,
bottom, top);
}
void rectangle_apply_at(int id, int left_index, int right_index,
const Coordinate &left, const Coordinate &right,
const Coordinate &bottom, const Coordinate &top,
const Value &multiplier, const Value &addend) {
const node ¤t = tree_[id];
if (disjoint(current, left, right, bottom, top)) {
return;
}
if (contained(current, left, right, bottom, top)) {
apply_node(id, multiplier, addend);
return;
}
push(id);
int middle = (left_index + right_index) / 2;
rectangle_apply_at(id * 2, left_index, middle, left, right, bottom, top,
multiplier, addend);
rectangle_apply_at(id * 2 + 1, middle, right_index, left, right, bottom,
top, multiplier, addend);
pull(id);
}
};
} // namespace noya