sparse_fenwick_2d.hpp¶
Offline-built sparse two-dimensional Fenwick tree. Register every coordinate that may later be updated, then call build(). An x-Fenwick node stores only the registered y-coordinates contributing to it, so the dense coordinate plane is replaced by O(p log p) cells.
在坐标稀疏的二维平面上执行点加与矩形和查询；只为实际出现的坐标分配空间。
Implementation¶
#ifndef NOYA_SPARSE_FENWICK_2D_HPP
#define NOYA_SPARSE_FENWICK_2D_HPP 1
/// @complexity Time: O(p log^2 p) registration/build and O(log^2 p) per point
/// addition, prefix sum, or rectangle sum. Space: O(p log p).
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline-built sparse two-dimensional Fenwick tree.
/// Register every coordinate that may later be updated, then call build().
/// An x-Fenwick node stores only the registered y-coordinates contributing to
/// it, so the dense coordinate plane is replaced by O(p log p) cells.
template <class T, class Coordinate = int> struct sparse_fenwick_2d {
std::vector<std::pair<Coordinate, Coordinate>> registered;
std::vector<Coordinate> xs;
std::vector<std::vector<Coordinate>> ys;
std::vector<std::vector<T>> data;
bool built = false;
/// @brief Remove all registered coordinates and values.
void clear() {
registered.clear();
xs.clear();
ys.clear();
data.clear();
built = false;
}
/// @brief Register a coordinate that may be passed to add() after build().
void reserve(Coordinate x, Coordinate y) {
assert(!built);
registered.emplace_back(x, y);
}
/// @brief Build the compressed Fenwick nodes with every value initially zero.
void build() {
assert(!built);
xs.reserve(registered.size());
for (auto [x, y] : registered) {
(void)y;
xs.push_back(x);
}
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
ys.assign(xs.size() + 1, {});
for (auto [x, y] : registered) {
int index = int(std::lower_bound(xs.begin(), xs.end(), x) - xs.begin());
for (index++; index <= int(xs.size()); index += index & -index) {
ys[index].push_back(y);
}
}
data.resize(xs.size() + 1);
for (int index = 1; index <= int(xs.size()); index++) {
auto &coordinates = ys[index];
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(std::unique(coordinates.begin(), coordinates.end()),
coordinates.end());
data[index].assign(coordinates.size() + 1, T{});
}
registered.clear();
registered.shrink_to_fit();
built = true;
}
/// @brief Add delta at a coordinate registered before build().
void add(Coordinate x, Coordinate y, const T &delta) {
assert(built);
auto x_iterator = std::lower_bound(xs.begin(), xs.end(), x);
assert(x_iterator != xs.end() && *x_iterator == x);
int x_index = int(x_iterator - xs.begin()) + 1;
for (; x_index <= int(xs.size()); x_index += x_index & -x_index) {
auto y_iterator = std::lower_bound(ys[x_index].begin(), ys[x_index].end(), y);
assert(y_iterator != ys[x_index].end() && *y_iterator == y);
int y_index = int(y_iterator - ys[x_index].begin()) + 1;
for (; y_index < int(data[x_index].size()); y_index += y_index & -y_index) {
data[x_index][y_index] += delta;
}
}
}
/// @brief Sum values at coordinates (px, py) with px < x and py < y.
T prefix_sum(Coordinate x, Coordinate y) const {
assert(built);
int x_index = int(std::lower_bound(xs.begin(), xs.end(), x) - xs.begin());
T result{};
for (; x_index > 0; x_index -= x_index & -x_index) {
int y_index = int(std::lower_bound(ys[x_index].begin(), ys[x_index].end(), y) -
ys[x_index].begin());
for (; y_index > 0; y_index -= y_index & -y_index) {
result += data[x_index][y_index];
}
}
return result;
}
/// @brief Sum values at coordinates (px, py) with px <= x and py <= y.
T prefix_sum_inclusive(Coordinate x, Coordinate y) const {
assert(built);
int x_index = int(std::upper_bound(xs.begin(), xs.end(), x) - xs.begin());
T result{};
for (; x_index > 0; x_index -= x_index & -x_index) {
int y_index = int(std::upper_bound(ys[x_index].begin(), ys[x_index].end(), y) -
ys[x_index].begin());
for (; y_index > 0; y_index -= y_index & -y_index) {
result += data[x_index][y_index];
}
}
return result;
}
/// @brief Sum values in [left, right) x [down, up).
T rectangle_sum(Coordinate left, Coordinate right, Coordinate down,
Coordinate up) const {
return prefix_sum(right, up) - prefix_sum(left, up) -
prefix_sum(right, down) + prefix_sum(left, down);
}
};
} // namespace noya
#endif // NOYA_SPARSE_FENWICK_2D_HPP
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
/// @complexity Time: O(p log^2 p) registration/build and O(log^2 p) per point
/// addition, prefix sum, or rectangle sum. Space: O(p log p).
namespace noya {
/// @brief Offline-built sparse two-dimensional Fenwick tree.
/// Register every coordinate that may later be updated, then call build().
/// An x-Fenwick node stores only the registered y-coordinates contributing to
/// it, so the dense coordinate plane is replaced by O(p log p) cells.
template <class T, class Coordinate = int> struct sparse_fenwick_2d {
std::vector<std::pair<Coordinate, Coordinate>> registered;
std::vector<Coordinate> xs;
std::vector<std::vector<Coordinate>> ys;
std::vector<std::vector<T>> data;
bool built = false;
/// @brief Remove all registered coordinates and values.
void clear() {
registered.clear();
xs.clear();
ys.clear();
data.clear();
built = false;
}
/// @brief Register a coordinate that may be passed to add() after build().
void reserve(Coordinate x, Coordinate y) {
assert(!built);
registered.emplace_back(x, y);
}
/// @brief Build the compressed Fenwick nodes with every value initially zero.
void build() {
assert(!built);
xs.reserve(registered.size());
for (auto [x, y] : registered) {
(void)y;
xs.push_back(x);
}
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
ys.assign(xs.size() + 1, {});
for (auto [x, y] : registered) {
int index = int(std::lower_bound(xs.begin(), xs.end(), x) - xs.begin());
for (index++; index <= int(xs.size()); index += index & -index) {
ys[index].push_back(y);
}
}
data.resize(xs.size() + 1);
for (int index = 1; index <= int(xs.size()); index++) {
auto &coordinates = ys[index];
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(std::unique(coordinates.begin(), coordinates.end()),
coordinates.end());
data[index].assign(coordinates.size() + 1, T{});
}
registered.clear();
registered.shrink_to_fit();
built = true;
}
/// @brief Add delta at a coordinate registered before build().
void add(Coordinate x, Coordinate y, const T &delta) {
assert(built);
auto x_iterator = std::lower_bound(xs.begin(), xs.end(), x);
assert(x_iterator != xs.end() && *x_iterator == x);
int x_index = int(x_iterator - xs.begin()) + 1;
for (; x_index <= int(xs.size()); x_index += x_index & -x_index) {
auto y_iterator = std::lower_bound(ys[x_index].begin(), ys[x_index].end(), y);
assert(y_iterator != ys[x_index].end() && *y_iterator == y);
int y_index = int(y_iterator - ys[x_index].begin()) + 1;
for (; y_index < int(data[x_index].size()); y_index += y_index & -y_index) {
data[x_index][y_index] += delta;
}
}
}
/// @brief Sum values at coordinates (px, py) with px < x and py < y.
T prefix_sum(Coordinate x, Coordinate y) const {
assert(built);
int x_index = int(std::lower_bound(xs.begin(), xs.end(), x) - xs.begin());
T result{};
for (; x_index > 0; x_index -= x_index & -x_index) {
int y_index = int(std::lower_bound(ys[x_index].begin(), ys[x_index].end(), y) -
ys[x_index].begin());
for (; y_index > 0; y_index -= y_index & -y_index) {
result += data[x_index][y_index];
}
}
return result;
}
/// @brief Sum values at coordinates (px, py) with px <= x and py <= y.
T prefix_sum_inclusive(Coordinate x, Coordinate y) const {
assert(built);
int x_index = int(std::upper_bound(xs.begin(), xs.end(), x) - xs.begin());
T result{};
for (; x_index > 0; x_index -= x_index & -x_index) {
int y_index = int(std::upper_bound(ys[x_index].begin(), ys[x_index].end(), y) -
ys[x_index].begin());
for (; y_index > 0; y_index -= y_index & -y_index) {
result += data[x_index][y_index];
}
}
return result;
}
/// @brief Sum values in [left, right) x [down, up).
T rectangle_sum(Coordinate left, Coordinate right, Coordinate down,
Coordinate up) const {
return prefix_sum(right, up) - prefix_sum(left, up) -
prefix_sum(right, down) + prefix_sum(left, down);
}
};
} // namespace noya