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 <bit>
#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);
if (xl == xr || yl == yr)
return T{};
if (xl == 0 && yl == 0)
return prefix_sum(xr, yr);
// Equal ancestors in the two prefix paths cancel in each dimension.
auto common = [](unsigned l, unsigned r) {
int bits = std::bit_width(l ^ r);
return int((l >> bits) << bits);
};
int xs = common(xl, xr), ys = common(yl, yr);
auto sum = [&](int row, int col) {
T value{};
for (int x = row; x > xs; x -= x & -x)
for (int y = col; y > ys; y -= y & -y)
value += dat[x][y];
return value;
};
return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
}
};
} // namespace noya
// NOYA_FENWICK_2D_HPP
#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 <bit>
#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);
if (xl == xr || yl == yr)
return T{};
if (xl == 0 && yl == 0)
return prefix_sum(xr, yr);
// Equal ancestors in the two prefix paths cancel in each dimension.
auto common = [](unsigned l, unsigned r) {
int bits = std::bit_width(l ^ r);
return int((l >> bits) << bits);
};
int xs = common(xl, xr), ys = common(yl, yr);
auto sum = [&](int row, int col) {
T value{};
for (int x = row; x > xs; x -= x & -x)
for (int y = col; y > ys; y -= y & -y)
value += dat[x][y];
return value;
};
return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
}
};
} // namespace noya
#endif // NOYA_FENWICK_2D_HPP
/// @complexity Time: O(log R log C) point update or rectangle query.
/// Space: O(RC).
#include <cassert>
#include <bit>
#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);
if (xl == xr || yl == yr)
return T{};
if (xl == 0 && yl == 0)
return prefix_sum(xr, yr);
// Equal ancestors in the two prefix paths cancel in each dimension.
auto common = [](unsigned l, unsigned r) {
int bits = std::bit_width(l ^ r);
return int((l >> bits) << bits);
};
int xs = common(xl, xr), ys = common(yl, yr);
auto sum = [&](int row, int col) {
T value{};
for (int x = row; x > xs; x -= x & -x)
for (int y = col; y > ys; y -= y & -y)
value += dat[x][y];
return value;
};
return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
}
};
} // namespace noya
// NOYA_FENWICK_2D_HPP