rectangle_add_rectangle_sum.hpp¶
离线处理二维矩形加权与矩形求和；适合更新和查询双方都是轴对齐矩形的覆盖贡献问题。
Complexity: Time: O(log R log C) per dense-grid operation, or O((N + Q) log(N + Q)) for the offline sparse-coordinate algorithm. Space: O(RC) for the dense structure or O(N + Q) offline.
AC 记录：static_rectangle_add_rectangle_sum。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log R log C) per dense-grid operation, or
/// O((N + Q) log(N + Q)) for the offline sparse-coordinate algorithm.
/// Space: O(RC) for the dense structure or O(N + Q) offline.
#include "noya/fenwick_2d.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>
namespace noya {
/// @brief Dense grid supporting half-open rectangle additions and rectangle
/// sum queries in O(log rows log columns), using four 2D Fenwick trees.
template <class T> struct rectangle_add_rectangle_sum {
int n = 0;
int m = 0;
fenwick_2d<T> c;
fenwick_2d<T> bx;
fenwick_2d<T> by;
fenwick_2d<T> bxy;
rectangle_add_rectangle_sum() = default;
rectangle_add_rectangle_sum(int n0, int m0) { build(n0, m0); }
void build(int n0, int m0) {
assert(n0 >= 0 && m0 >= 0);
n = n0;
m = m0;
c.build(n + 1, m + 1);
bx.build(n + 1, m + 1);
by.build(n + 1, m + 1);
bxy.build(n + 1, m + 1);
}
void add(int xl, int xr, int yl, int yr, const T &dif) {
assert(0 <= xl && xl <= xr && xr <= n);
assert(0 <= yl && yl <= yr && yr <= m);
corner(xl, yl, dif);
corner(xl, yr, -dif);
corner(xr, yl, -dif);
corner(xr, yr, dif);
}
T prefix_sum(int row, int y0) const {
assert(0 <= row && row <= n);
assert(0 <= y0 && y0 <= m);
return c.prefix_sum(row, y0) * T(row) * T(y0) -
bx.prefix_sum(row, y0) * T(y0) - by.prefix_sum(row, y0) * T(row) +
bxy.prefix_sum(row, y0);
}
T 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);
}
private:
void corner(int row, int y0, const T &dif) {
c.add(row, y0, dif);
bx.add(row, y0, dif * T(row));
by.add(row, y0, dif * T(y0));
bxy.add(row, y0, dif * T(row) * T(y0));
}
};
template <class Coordinate, class T> struct weighted_rectangle {
Coordinate l;
Coordinate d;
Coordinate r;
Coordinate up;
T w;
};
template <class Coordinate> struct rectangle_query {
Coordinate l;
Coordinate d;
Coordinate r;
Coordinate up;
};
/// @brief Answer static rectangle-add rectangle-sum queries on sparse
/// coordinates. A rectangle is four signed corners. For a prefix ending at
/// (x,y), each dominated corner (a,b,w) contributes
/// `w (x-a) (y-b)`; expanding this product leaves four coefficient sums, all
/// maintained by one x-sweep and a Fenwick tree over compressed y-coordinates.
template <class Coordinate, class T>
std::vector<T> offline_rectangle_add_rectangle_sum(
const std::vector<weighted_rectangle<Coordinate, T>> &upd,
const std::vector<rectangle_query<Coordinate>> &qs) {
struct event {
Coordinate x;
Coordinate y;
T w;
};
struct prefix_query {
Coordinate x;
Coordinate y;
int idx;
int sgn;
};
struct coefficients {
T c{};
T x{};
T y{};
T xy{};
coefficients &operator+=(const coefficients &rhs) {
c += rhs.c;
x += rhs.x;
y += rhs.y;
xy += rhs.xy;
return *this;
}
};
std::vector<event> es;
std::vector<Coordinate> ys;
es.reserve(upd.size() * 4);
ys.reserve(upd.size() * 2);
for (const auto &up0 : upd) {
assert(up0.l <= up0.r && up0.d <= up0.up);
es.push_back({up0.l, up0.d, up0.w});
es.push_back({up0.l, up0.up, -up0.w});
es.push_back({up0.r, up0.d, -up0.w});
es.push_back({up0.r, up0.up, up0.w});
ys.push_back(up0.d);
ys.push_back(up0.up);
}
std::sort(es.begin(), es.end(),
[](const event &a, const event &b) { return a.x < b.x; });
std::sort(ys.begin(), ys.end());
ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
std::vector<prefix_query> pt;
pt.reserve(qs.size() * 4);
for (int idx = 0; idx < int(qs.size()); idx++) {
const auto &q = qs[idx];
assert(q.l <= q.r && q.d <= q.up);
pt.push_back({q.r, q.up, idx, 1});
pt.push_back({q.l, q.up, idx, -1});
pt.push_back({q.r, q.d, idx, -1});
pt.push_back({q.l, q.d, idx, 1});
}
std::sort(
pt.begin(), pt.end(),
[](const prefix_query &a, const prefix_query &b) { return a.x < b.x; });
std::vector<coefficients> bit(ys.size() + 1);
auto add = [&](int pos, const coefficients &val) {
for (pos++; pos < int(bit.size()); pos += pos & -pos) {
bit[pos] += val;
}
};
auto pre = [&](int r) {
coefficients res;
for (; r > 0; r -= r & -r) {
res += bit[r];
}
return res;
};
std::vector<T> ans(qs.size());
std::size_t ei = 0;
for (const auto &pt0 : pt) {
while (ei < es.size() && es[ei].x <= pt0.x) {
const auto &cur = es[ei++];
T x = T(cur.x);
T y = T(cur.y);
add(int(std::lower_bound(ys.begin(), ys.end(), cur.y) - ys.begin()),
{cur.w, cur.w * x, cur.w * y, cur.w * x * y});
}
int rk = int(std::upper_bound(ys.begin(), ys.end(), pt0.y) - ys.begin());
coefficients sum = pre(rk);
T x = T(pt0.x);
T y = T(pt0.y);
T val = x * y * sum.c - y * sum.x - x * sum.y + sum.xy;
if (pt0.sgn > 0) {
ans[pt0.idx] += val;
} else {
ans[pt0.idx] -= val;
}
}
return ans;
}
} // namespace noya
#ifndef NOYA_RECTANGLE_ADD_RECTANGLE_SUM_HPP
#define NOYA_RECTANGLE_ADD_RECTANGLE_SUM_HPP 1
/// @complexity Time: O(log R log C) per dense-grid operation, or
/// O((N + Q) log(N + Q)) for the offline sparse-coordinate algorithm.
/// Space: O(RC) for the dense structure or O(N + Q) offline.
#include "noya/fenwick_2d.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>
namespace noya {
/// @brief Dense grid supporting half-open rectangle additions and rectangle
/// sum queries in O(log rows log columns), using four 2D Fenwick trees.
template <class T> struct rectangle_add_rectangle_sum {
int n = 0;
int m = 0;
fenwick_2d<T> c;
fenwick_2d<T> bx;
fenwick_2d<T> by;
fenwick_2d<T> bxy;
rectangle_add_rectangle_sum() = default;
rectangle_add_rectangle_sum(int n0, int m0) { build(n0, m0); }
void build(int n0, int m0) {
assert(n0 >= 0 && m0 >= 0);
n = n0;
m = m0;
c.build(n + 1, m + 1);
bx.build(n + 1, m + 1);
by.build(n + 1, m + 1);
bxy.build(n + 1, m + 1);
}
void add(int xl, int xr, int yl, int yr, const T &dif) {
assert(0 <= xl && xl <= xr && xr <= n);
assert(0 <= yl && yl <= yr && yr <= m);
corner(xl, yl, dif);
corner(xl, yr, -dif);
corner(xr, yl, -dif);
corner(xr, yr, dif);
}
T prefix_sum(int row, int y0) const {
assert(0 <= row && row <= n);
assert(0 <= y0 && y0 <= m);
return c.prefix_sum(row, y0) * T(row) * T(y0) -
bx.prefix_sum(row, y0) * T(y0) - by.prefix_sum(row, y0) * T(row) +
bxy.prefix_sum(row, y0);
}
T 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);
}
private:
void corner(int row, int y0, const T &dif) {
c.add(row, y0, dif);
bx.add(row, y0, dif * T(row));
by.add(row, y0, dif * T(y0));
bxy.add(row, y0, dif * T(row) * T(y0));
}
};
template <class Coordinate, class T> struct weighted_rectangle {
Coordinate l;
Coordinate d;
Coordinate r;
Coordinate up;
T w;
};
template <class Coordinate> struct rectangle_query {
Coordinate l;
Coordinate d;
Coordinate r;
Coordinate up;
};
/// @brief Answer static rectangle-add rectangle-sum queries on sparse
/// coordinates. A rectangle is four signed corners. For a prefix ending at
/// (x,y), each dominated corner (a,b,w) contributes
/// `w (x-a) (y-b)`; expanding this product leaves four coefficient sums, all
/// maintained by one x-sweep and a Fenwick tree over compressed y-coordinates.
template <class Coordinate, class T>
std::vector<T> offline_rectangle_add_rectangle_sum(
const std::vector<weighted_rectangle<Coordinate, T>> &upd,
const std::vector<rectangle_query<Coordinate>> &qs) {
struct event {
Coordinate x;
Coordinate y;
T w;
};
struct prefix_query {
Coordinate x;
Coordinate y;
int idx;
int sgn;
};
struct coefficients {
T c{};
T x{};
T y{};
T xy{};
coefficients &operator+=(const coefficients &rhs) {
c += rhs.c;
x += rhs.x;
y += rhs.y;
xy += rhs.xy;
return *this;
}
};
std::vector<event> es;
std::vector<Coordinate> ys;
es.reserve(upd.size() * 4);
ys.reserve(upd.size() * 2);
for (const auto &up0 : upd) {
assert(up0.l <= up0.r && up0.d <= up0.up);
es.push_back({up0.l, up0.d, up0.w});
es.push_back({up0.l, up0.up, -up0.w});
es.push_back({up0.r, up0.d, -up0.w});
es.push_back({up0.r, up0.up, up0.w});
ys.push_back(up0.d);
ys.push_back(up0.up);
}
std::sort(es.begin(), es.end(),
[](const event &a, const event &b) { return a.x < b.x; });
std::sort(ys.begin(), ys.end());
ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
std::vector<prefix_query> pt;
pt.reserve(qs.size() * 4);
for (int idx = 0; idx < int(qs.size()); idx++) {
const auto &q = qs[idx];
assert(q.l <= q.r && q.d <= q.up);
pt.push_back({q.r, q.up, idx, 1});
pt.push_back({q.l, q.up, idx, -1});
pt.push_back({q.r, q.d, idx, -1});
pt.push_back({q.l, q.d, idx, 1});
}
std::sort(
pt.begin(), pt.end(),
[](const prefix_query &a, const prefix_query &b) { return a.x < b.x; });
std::vector<coefficients> bit(ys.size() + 1);
auto add = [&](int pos, const coefficients &val) {
for (pos++; pos < int(bit.size()); pos += pos & -pos) {
bit[pos] += val;
}
};
auto pre = [&](int r) {
coefficients res;
for (; r > 0; r -= r & -r) {
res += bit[r];
}
return res;
};
std::vector<T> ans(qs.size());
std::size_t ei = 0;
for (const auto &pt0 : pt) {
while (ei < es.size() && es[ei].x <= pt0.x) {
const auto &cur = es[ei++];
T x = T(cur.x);
T y = T(cur.y);
add(int(std::lower_bound(ys.begin(), ys.end(), cur.y) - ys.begin()),
{cur.w, cur.w * x, cur.w * y, cur.w * x * y});
}
int rk = int(std::upper_bound(ys.begin(), ys.end(), pt0.y) - ys.begin());
coefficients sum = pre(rk);
T x = T(pt0.x);
T y = T(pt0.y);
T val = x * y * sum.c - y * sum.x - x * sum.y + sum.xy;
if (pt0.sgn > 0) {
ans[pt0.idx] += val;
} else {
ans[pt0.idx] -= val;
}
}
return ans;
}
} // namespace noya
#endif // NOYA_RECTANGLE_ADD_RECTANGLE_SUM_HPP
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>
/// @complexity Time: O(log R log C) per dense-grid operation, or
/// O((N + Q) log(N + Q)) for the offline sparse-coordinate algorithm.
/// Space: O(RC) for the dense structure or O(N + Q) offline.
/// @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
namespace noya {
/// @brief Dense grid supporting half-open rectangle additions and rectangle
/// sum queries in O(log rows log columns), using four 2D Fenwick trees.
template <class T> struct rectangle_add_rectangle_sum {
int n = 0;
int m = 0;
fenwick_2d<T> c;
fenwick_2d<T> bx;
fenwick_2d<T> by;
fenwick_2d<T> bxy;
rectangle_add_rectangle_sum() = default;
rectangle_add_rectangle_sum(int n0, int m0) { build(n0, m0); }
void build(int n0, int m0) {
assert(n0 >= 0 && m0 >= 0);
n = n0;
m = m0;
c.build(n + 1, m + 1);
bx.build(n + 1, m + 1);
by.build(n + 1, m + 1);
bxy.build(n + 1, m + 1);
}
void add(int xl, int xr, int yl, int yr, const T &dif) {
assert(0 <= xl && xl <= xr && xr <= n);
assert(0 <= yl && yl <= yr && yr <= m);
corner(xl, yl, dif);
corner(xl, yr, -dif);
corner(xr, yl, -dif);
corner(xr, yr, dif);
}
T prefix_sum(int row, int y0) const {
assert(0 <= row && row <= n);
assert(0 <= y0 && y0 <= m);
return c.prefix_sum(row, y0) * T(row) * T(y0) -
bx.prefix_sum(row, y0) * T(y0) - by.prefix_sum(row, y0) * T(row) +
bxy.prefix_sum(row, y0);
}
T 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);
}
private:
void corner(int row, int y0, const T &dif) {
c.add(row, y0, dif);
bx.add(row, y0, dif * T(row));
by.add(row, y0, dif * T(y0));
bxy.add(row, y0, dif * T(row) * T(y0));
}
};
template <class Coordinate, class T> struct weighted_rectangle {
Coordinate l;
Coordinate d;
Coordinate r;
Coordinate up;
T w;
};
template <class Coordinate> struct rectangle_query {
Coordinate l;
Coordinate d;
Coordinate r;
Coordinate up;
};
/// @brief Answer static rectangle-add rectangle-sum queries on sparse
/// coordinates. A rectangle is four signed corners. For a prefix ending at
/// (x,y), each dominated corner (a,b,w) contributes
/// `w (x-a) (y-b)`; expanding this product leaves four coefficient sums, all
/// maintained by one x-sweep and a Fenwick tree over compressed y-coordinates.
template <class Coordinate, class T>
std::vector<T> offline_rectangle_add_rectangle_sum(
const std::vector<weighted_rectangle<Coordinate, T>> &upd,
const std::vector<rectangle_query<Coordinate>> &qs) {
struct event {
Coordinate x;
Coordinate y;
T w;
};
struct prefix_query {
Coordinate x;
Coordinate y;
int idx;
int sgn;
};
struct coefficients {
T c{};
T x{};
T y{};
T xy{};
coefficients &operator+=(const coefficients &rhs) {
c += rhs.c;
x += rhs.x;
y += rhs.y;
xy += rhs.xy;
return *this;
}
};
std::vector<event> es;
std::vector<Coordinate> ys;
es.reserve(upd.size() * 4);
ys.reserve(upd.size() * 2);
for (const auto &up0 : upd) {
assert(up0.l <= up0.r && up0.d <= up0.up);
es.push_back({up0.l, up0.d, up0.w});
es.push_back({up0.l, up0.up, -up0.w});
es.push_back({up0.r, up0.d, -up0.w});
es.push_back({up0.r, up0.up, up0.w});
ys.push_back(up0.d);
ys.push_back(up0.up);
}
std::sort(es.begin(), es.end(),
[](const event &a, const event &b) { return a.x < b.x; });
std::sort(ys.begin(), ys.end());
ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
std::vector<prefix_query> pt;
pt.reserve(qs.size() * 4);
for (int idx = 0; idx < int(qs.size()); idx++) {
const auto &q = qs[idx];
assert(q.l <= q.r && q.d <= q.up);
pt.push_back({q.r, q.up, idx, 1});
pt.push_back({q.l, q.up, idx, -1});
pt.push_back({q.r, q.d, idx, -1});
pt.push_back({q.l, q.d, idx, 1});
}
std::sort(
pt.begin(), pt.end(),
[](const prefix_query &a, const prefix_query &b) { return a.x < b.x; });
std::vector<coefficients> bit(ys.size() + 1);
auto add = [&](int pos, const coefficients &val) {
for (pos++; pos < int(bit.size()); pos += pos & -pos) {
bit[pos] += val;
}
};
auto pre = [&](int r) {
coefficients res;
for (; r > 0; r -= r & -r) {
res += bit[r];
}
return res;
};
std::vector<T> ans(qs.size());
std::size_t ei = 0;
for (const auto &pt0 : pt) {
while (ei < es.size() && es[ei].x <= pt0.x) {
const auto &cur = es[ei++];
T x = T(cur.x);
T y = T(cur.y);
add(int(std::lower_bound(ys.begin(), ys.end(), cur.y) - ys.begin()),
{cur.w, cur.w * x, cur.w * y, cur.w * x * y});
}
int rk = int(std::upper_bound(ys.begin(), ys.end(), pt0.y) - ys.begin());
coefficients sum = pre(rk);
T x = T(pt0.x);
T y = T(pt0.y);
T val = x * y * sum.c - y * sum.x - x * sum.y + sum.xy;
if (pt0.sgn > 0) {
ans[pt0.idx] += val;
} else {
ans[pt0.idx] -= val;
}
}
return ans;
}
} // namespace noya