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/ds/fenwick_2d.hpp"
#include <algorithm>
#include <array>
#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);
if (xl == xr || yl == yr) {
return;
}
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);
// The four coefficient sums use the same prefix path.
T sc{}, sx{}, sy{}, sxy{};
for (int x = row; x > 0; x -= x & -x) {
for (int y = y0; y > 0; y -= y & -y) {
sc += c.dat[x][y];
sx += bx.dat[x][y];
sy += by.dat[x][y];
sxy += bxy.dat[x][y];
}
}
return sc * T(row) * T(y0) - sx * T(y0) - sy * T(row) + sxy;
}
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);
if (xl == xr || yl == yr) {
return T{};
}
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;
int d;
int up;
T w;
};
struct prefix_query {
Coordinate x;
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<T> ans(qs.size());
if (qs.empty()) {
return ans;
}
std::vector<Coordinate> ys;
ys.reserve(upd.size() * 2);
for (const auto &up0 : upd) {
assert(up0.l <= up0.r && up0.d <= up0.up);
if (up0.l == up0.r || up0.d == up0.up) {
continue;
}
ys.push_back(up0.d);
ys.push_back(up0.up);
}
if (ys.empty()) {
return ans;
}
std::sort(ys.begin(), ys.end());
ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
// Keep the two y endpoints of each vertical edge in one sorted record.
std::vector<event> es;
es.reserve(upd.size() * 2);
for (const auto &up0 : upd) {
if (up0.l == up0.r || up0.d == up0.up) {
continue;
}
int d = int(std::lower_bound(ys.begin(), ys.end(), up0.d) - ys.begin());
int u = int(std::lower_bound(ys.begin(), ys.end(), up0.up) - ys.begin());
es.push_back({up0.l, d, u, up0.w});
es.push_back({up0.r, u, d, up0.w});
}
std::sort(es.begin(), es.end(),
[](const event &a, const event &b) { return a.x < b.x; });
std::vector<prefix_query> pt;
pt.reserve(qs.size() * 2);
std::vector<std::array<int, 2>> ranks(qs.size());
for (int idx = 0; idx < int(qs.size()); idx++) {
const auto &q = qs[idx];
assert(q.l <= q.r && q.d <= q.up);
if (q.l == q.r || q.d == q.up) {
continue;
}
ranks[idx] = {
int(std::upper_bound(ys.begin(), ys.end(), q.d) - ys.begin()),
int(std::upper_bound(ys.begin(), ys.end(), q.up) - ys.begin())};
pt.push_back({q.r, idx, 1});
pt.push_back({q.l, 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::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 d = T(ys[cur.d]), u = T(ys[cur.up]);
T wx = cur.w * x;
add(cur.d, {cur.w, wx, cur.w * d, wx * d});
add(cur.up, {-cur.w, -wx, -cur.w * u, -wx * u});
}
T x = T(pt0.x);
auto evaluate = [&](int rk, Coordinate y0) {
coefficients sum = pre(rk);
T y = T(y0);
return x * y * sum.c - y * sum.x - x * sum.y + sum.xy;
};
const auto &q = qs[pt0.idx];
T val = evaluate(ranks[pt0.idx][1], q.up) -
evaluate(ranks[pt0.idx][0], q.d);
if (pt0.sgn > 0) {
ans[pt0.idx] += val;
} else {
ans[pt0.idx] -= val;
}
}
return ans;
}
} // namespace noya
// NOYA_RECTANGLE_ADD_RECTANGLE_SUM_HPP
#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/ds/fenwick_2d.hpp"
#include <algorithm>
#include <array>
#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);
if (xl == xr || yl == yr) {
return;
}
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);
// The four coefficient sums use the same prefix path.
T sc{}, sx{}, sy{}, sxy{};
for (int x = row; x > 0; x -= x & -x) {
for (int y = y0; y > 0; y -= y & -y) {
sc += c.dat[x][y];
sx += bx.dat[x][y];
sy += by.dat[x][y];
sxy += bxy.dat[x][y];
}
}
return sc * T(row) * T(y0) - sx * T(y0) - sy * T(row) + sxy;
}
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);
if (xl == xr || yl == yr) {
return T{};
}
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;
int d;
int up;
T w;
};
struct prefix_query {
Coordinate x;
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<T> ans(qs.size());
if (qs.empty()) {
return ans;
}
std::vector<Coordinate> ys;
ys.reserve(upd.size() * 2);
for (const auto &up0 : upd) {
assert(up0.l <= up0.r && up0.d <= up0.up);
if (up0.l == up0.r || up0.d == up0.up) {
continue;
}
ys.push_back(up0.d);
ys.push_back(up0.up);
}
if (ys.empty()) {
return ans;
}
std::sort(ys.begin(), ys.end());
ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
// Keep the two y endpoints of each vertical edge in one sorted record.
std::vector<event> es;
es.reserve(upd.size() * 2);
for (const auto &up0 : upd) {
if (up0.l == up0.r || up0.d == up0.up) {
continue;
}
int d = int(std::lower_bound(ys.begin(), ys.end(), up0.d) - ys.begin());
int u = int(std::lower_bound(ys.begin(), ys.end(), up0.up) - ys.begin());
es.push_back({up0.l, d, u, up0.w});
es.push_back({up0.r, u, d, up0.w});
}
std::sort(es.begin(), es.end(),
[](const event &a, const event &b) { return a.x < b.x; });
std::vector<prefix_query> pt;
pt.reserve(qs.size() * 2);
std::vector<std::array<int, 2>> ranks(qs.size());
for (int idx = 0; idx < int(qs.size()); idx++) {
const auto &q = qs[idx];
assert(q.l <= q.r && q.d <= q.up);
if (q.l == q.r || q.d == q.up) {
continue;
}
ranks[idx] = {
int(std::upper_bound(ys.begin(), ys.end(), q.d) - ys.begin()),
int(std::upper_bound(ys.begin(), ys.end(), q.up) - ys.begin())};
pt.push_back({q.r, idx, 1});
pt.push_back({q.l, 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::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 d = T(ys[cur.d]), u = T(ys[cur.up]);
T wx = cur.w * x;
add(cur.d, {cur.w, wx, cur.w * d, wx * d});
add(cur.up, {-cur.w, -wx, -cur.w * u, -wx * u});
}
T x = T(pt0.x);
auto evaluate = [&](int rk, Coordinate y0) {
coefficients sum = pre(rk);
T y = T(y0);
return x * y * sum.c - y * sum.x - x * sum.y + sum.xy;
};
const auto &q = qs[pt0.idx];
T val = evaluate(ranks[pt0.idx][1], q.up) -
evaluate(ranks[pt0.idx][0], q.d);
if (pt0.sgn > 0) {
ans[pt0.idx] += val;
} else {
ans[pt0.idx] -= val;
}
}
return ans;
}
} // namespace noya
#endif // NOYA_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.
/// @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
#include <algorithm>
#include <array>
#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);
if (xl == xr || yl == yr) {
return;
}
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);
// The four coefficient sums use the same prefix path.
T sc{}, sx{}, sy{}, sxy{};
for (int x = row; x > 0; x -= x & -x) {
for (int y = y0; y > 0; y -= y & -y) {
sc += c.dat[x][y];
sx += bx.dat[x][y];
sy += by.dat[x][y];
sxy += bxy.dat[x][y];
}
}
return sc * T(row) * T(y0) - sx * T(y0) - sy * T(row) + sxy;
}
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);
if (xl == xr || yl == yr) {
return T{};
}
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;
int d;
int up;
T w;
};
struct prefix_query {
Coordinate x;
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<T> ans(qs.size());
if (qs.empty()) {
return ans;
}
std::vector<Coordinate> ys;
ys.reserve(upd.size() * 2);
for (const auto &up0 : upd) {
assert(up0.l <= up0.r && up0.d <= up0.up);
if (up0.l == up0.r || up0.d == up0.up) {
continue;
}
ys.push_back(up0.d);
ys.push_back(up0.up);
}
if (ys.empty()) {
return ans;
}
std::sort(ys.begin(), ys.end());
ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
// Keep the two y endpoints of each vertical edge in one sorted record.
std::vector<event> es;
es.reserve(upd.size() * 2);
for (const auto &up0 : upd) {
if (up0.l == up0.r || up0.d == up0.up) {
continue;
}
int d = int(std::lower_bound(ys.begin(), ys.end(), up0.d) - ys.begin());
int u = int(std::lower_bound(ys.begin(), ys.end(), up0.up) - ys.begin());
es.push_back({up0.l, d, u, up0.w});
es.push_back({up0.r, u, d, up0.w});
}
std::sort(es.begin(), es.end(),
[](const event &a, const event &b) { return a.x < b.x; });
std::vector<prefix_query> pt;
pt.reserve(qs.size() * 2);
std::vector<std::array<int, 2>> ranks(qs.size());
for (int idx = 0; idx < int(qs.size()); idx++) {
const auto &q = qs[idx];
assert(q.l <= q.r && q.d <= q.up);
if (q.l == q.r || q.d == q.up) {
continue;
}
ranks[idx] = {
int(std::upper_bound(ys.begin(), ys.end(), q.d) - ys.begin()),
int(std::upper_bound(ys.begin(), ys.end(), q.up) - ys.begin())};
pt.push_back({q.r, idx, 1});
pt.push_back({q.l, 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::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 d = T(ys[cur.d]), u = T(ys[cur.up]);
T wx = cur.w * x;
add(cur.d, {cur.w, wx, cur.w * d, wx * d});
add(cur.up, {-cur.w, -wx, -cur.w * u, -wx * u});
}
T x = T(pt0.x);
auto evaluate = [&](int rk, Coordinate y0) {
coefficients sum = pre(rk);
T y = T(y0);
return x * y * sum.c - y * sum.x - x * sum.y + sum.xy;
};
const auto &q = qs[pt0.idx];
T val = evaluate(ranks[pt0.idx][1], q.up) -
evaluate(ranks[pt0.idx][0], q.d);
if (pt0.sgn > 0) {
ans[pt0.idx] += val;
} else {
ans[pt0.idx] -= val;
}
}
return ans;
}
} // namespace noya
// NOYA_RECTANGLE_ADD_RECTANGLE_SUM_HPP