fenwick_2d.hpp¶
在稠密二维网格上执行单点加法与矩形和查询；适合坐标范围可直接开二维树状数组的动态点权问题。
Complexity: Time: O(log R log C) point update or rectangle query. Space: O(RC).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 n = 0;
int m = 0;
std::vector<std::vector<T>> dat;
fenwick_2d() = default;
fenwick_2d(int n0, int m0) { build(n0, m0); }
/// @brief Reset to a rows by columns grid of zeros.
void build(int n0, int m0) {
assert(n0 >= 0 && m0 >= 0);
n = n0;
m = m0;
dat.assign(n + 1, std::vector<T>(m + 1));
}
/// @brief Add delta to cell (row, column).
void add(int row, int y0, const T &dif) {
assert(0 <= row && row < n);
assert(0 <= y0 && y0 < m);
for (int x = row + 1; x <= n; x += x & -x) {
for (int y = y0 + 1; y <= m; y += y & -y) {
dat[x][y] += dif;
}
}
}
/// @brief Return the sum over [0, row) x [0, y0).
T prefix_sum(int row, int y0) const {
assert(0 <= row && row <= n);
assert(0 <= y0 && y0 <= m);
T res{};
for (int x = row; x > 0; x -= x & -x) {
for (int y = y0; y > 0; y -= y & -y) {
res += dat[x][y];
}
}
return res;
}
/// @brief Return the sum over [xl, xr) x
/// [yl, yr).
T rectangle_sum(int xl, int xr, int yl, int yr) const {
assert(0 <= xl && xl <= xr && xr <= n);
assert(0 <= yl && yl <= yr && yr <= m);
return prefix_sum(xr, yr) - prefix_sum(xl, yr) - prefix_sum(xr, yl) +
prefix_sum(xl, yl);
}
};
} // namespace noya
#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 n = 0;
int m = 0;
std::vector<std::vector<T>> dat;
fenwick_2d() = default;
fenwick_2d(int n0, int m0) { build(n0, m0); }
/// @brief Reset to a rows by columns grid of zeros.
void build(int n0, int m0) {
assert(n0 >= 0 && m0 >= 0);
n = n0;
m = m0;
dat.assign(n + 1, std::vector<T>(m + 1));
}
/// @brief Add delta to cell (row, column).
void add(int row, int y0, const T &dif) {
assert(0 <= row && row < n);
assert(0 <= y0 && y0 < m);
for (int x = row + 1; x <= n; x += x & -x) {
for (int y = y0 + 1; y <= m; y += y & -y) {
dat[x][y] += dif;
}
}
}
/// @brief Return the sum over [0, row) x [0, y0).
T prefix_sum(int row, int y0) const {
assert(0 <= row && row <= n);
assert(0 <= y0 && y0 <= m);
T res{};
for (int x = row; x > 0; x -= x & -x) {
for (int y = y0; y > 0; y -= y & -y) {
res += dat[x][y];
}
}
return res;
}
/// @brief Return the sum over [xl, xr) x
/// [yl, yr).
T rectangle_sum(int xl, int xr, int yl, int yr) const {
assert(0 <= xl && xl <= xr && xr <= n);
assert(0 <= yl && yl <= yr && yr <= m);
return prefix_sum(xr, yr) - prefix_sum(xl, yr) - prefix_sum(xr, yl) +
prefix_sum(xl, yl);
}
};
} // 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 n = 0;
int m = 0;
std::vector<std::vector<T>> dat;
fenwick_2d() = default;
fenwick_2d(int n0, int m0) { build(n0, m0); }
/// @brief Reset to a rows by columns grid of zeros.
void build(int n0, int m0) {
assert(n0 >= 0 && m0 >= 0);
n = n0;
m = m0;
dat.assign(n + 1, std::vector<T>(m + 1));
}
/// @brief Add delta to cell (row, column).
void add(int row, int y0, const T &dif) {
assert(0 <= row && row < n);
assert(0 <= y0 && y0 < m);
for (int x = row + 1; x <= n; x += x & -x) {
for (int y = y0 + 1; y <= m; y += y & -y) {
dat[x][y] += dif;
}
}
}
/// @brief Return the sum over [0, row) x [0, y0).
T prefix_sum(int row, int y0) const {
assert(0 <= row && row <= n);
assert(0 <= y0 && y0 <= m);
T res{};
for (int x = row; x > 0; x -= x & -x) {
for (int y = y0; y > 0; y -= y & -y) {
res += dat[x][y];
}
}
return res;
}
/// @brief Return the sum over [xl, xr) x
/// [yl, yr).
T rectangle_sum(int xl, int xr, int yl, int yr) const {
assert(0 <= xl && xl <= xr && xr <= n);
assert(0 <= yl && yl <= yr && yr <= m);
return prefix_sum(xr, yr) - prefix_sum(xl, yr) - prefix_sum(xr, yl) +
prefix_sum(xl, yl);
}
};
} // namespace noya