fenwick_2d.hpp¶
Dense two-dimensional Fenwick tree for point additions and rectangle sums.
在稠密二维网格上执行单点加法与矩形和查询；适合坐标范围可直接开二维树状数组的动态点权问题。
Implementation¶
#ifndef NOYA_FENWICK_2D_HPP
#define NOYA_FENWICK_2D_HPP 1
/// @complexity Time: O(log R log C) point update or rectangle query.
/// Space: O(RC).
#include <cassert>
#include <vector>
namespace noya {
/// @brief Dense two-dimensional Fenwick tree for point additions and rectangle
/// sums.
template <class T> struct fenwick_2d {
int rows = 0;
int columns = 0;
std::vector<std::vector<T>> data;
fenwick_2d() = default;
fenwick_2d(int rows_, int columns_) { build(rows_, columns_); }
/// @brief Reset to a rows by columns grid of zeros.
void build(int rows_, int columns_) {
assert(rows_ >= 0 && columns_ >= 0);
rows = rows_;
columns = columns_;
data.assign(rows + 1, std::vector<T>(columns + 1));
}
/// @brief Add delta to cell (row, column).
void add(int row, int column, const T &delta) {
assert(0 <= row && row < rows);
assert(0 <= column && column < columns);
for (int x = row + 1; x <= rows; x += x & -x) {
for (int y = column + 1; y <= columns; y += y & -y) {
data[x][y] += delta;
}
}
}
/// @brief Return the sum over [0, row) x [0, column).
T prefix_sum(int row, int column) const {
assert(0 <= row && row <= rows);
assert(0 <= column && column <= columns);
T result{};
for (int x = row; x > 0; x -= x & -x) {
for (int y = column; y > 0; y -= y & -y) {
result += data[x][y];
}
}
return result;
}
/// @brief Return the sum over [row_left, row_right) x
/// [column_left, column_right).
T rectangle_sum(int row_left, int row_right, int column_left,
int column_right) const {
assert(0 <= row_left && row_left <= row_right && row_right <= rows);
assert(0 <= column_left && column_left <= column_right &&
column_right <= columns);
return prefix_sum(row_right, column_right) -
prefix_sum(row_left, column_right) -
prefix_sum(row_right, column_left) +
prefix_sum(row_left, column_left);
}
};
} // namespace noya
#endif // NOYA_FENWICK_2D_HPP
#include <cassert>
#include <vector>
/// @complexity Time: O(log R log C) point update or rectangle query.
/// Space: O(RC).
namespace noya {
/// @brief Dense two-dimensional Fenwick tree for point additions and rectangle
/// sums.
template <class T> struct fenwick_2d {
int rows = 0;
int columns = 0;
std::vector<std::vector<T>> data;
fenwick_2d() = default;
fenwick_2d(int rows_, int columns_) { build(rows_, columns_); }
/// @brief Reset to a rows by columns grid of zeros.
void build(int rows_, int columns_) {
assert(rows_ >= 0 && columns_ >= 0);
rows = rows_;
columns = columns_;
data.assign(rows + 1, std::vector<T>(columns + 1));
}
/// @brief Add delta to cell (row, column).
void add(int row, int column, const T &delta) {
assert(0 <= row && row < rows);
assert(0 <= column && column < columns);
for (int x = row + 1; x <= rows; x += x & -x) {
for (int y = column + 1; y <= columns; y += y & -y) {
data[x][y] += delta;
}
}
}
/// @brief Return the sum over [0, row) x [0, column).
T prefix_sum(int row, int column) const {
assert(0 <= row && row <= rows);
assert(0 <= column && column <= columns);
T result{};
for (int x = row; x > 0; x -= x & -x) {
for (int y = column; y > 0; y -= y & -y) {
result += data[x][y];
}
}
return result;
}
/// @brief Return the sum over [row_left, row_right) x
/// [column_left, column_right).
T rectangle_sum(int row_left, int row_right, int column_left,
int column_right) const {
assert(0 <= row_left && row_left <= row_right && row_right <= rows);
assert(0 <= column_left && column_left <= column_right &&
column_right <= columns);
return prefix_sum(row_right, column_right) -
prefix_sum(row_left, column_right) -
prefix_sum(row_right, column_left) +
prefix_sum(row_left, column_left);
}
};
} // namespace noya