C++ Library for Competitive Programming
#include "emthrm/data_structure/fenwick_tree/2d_fenwick_tree_supporting_range_add_query.hpp"
時間計算量 | |
---|---|
Fenwick tree | $\langle O(N), O(\log{N}) \rangle$ |
2次元 Fenwick tree | $\langle O(HW), O((\log{H})(\log{W})) \rangle$ |
template <typename Abelian>
struct FenwickTree;
Abelian
:アーベル群である要素型名前 | 効果・戻り値 | 要件 |
---|---|---|
explicit FenwickTree(const int n, const Abelian ID = 0); |
要素数 $N$、単位元 $\mathrm{id}$ のオブジェクトを構築する。 | |
void add(int idx, const Abelian val); |
$A_{\mathrm{idx}} \gets A_{\mathrm{idx}} + \mathrm{val}$ | |
Abelian sum(int idx) const; |
$\sum_{i = 0}^{\mathrm{idx} - 1} A_i$ | |
Abelian sum(const int left, const int right) const; |
$\sum_{i = \mathrm{left}}^{\mathrm{right} - 1} A_i$ | |
Abelian operator[](const int idx) const; |
$A_{\mathrm{idx}}$ | |
int lower_bound(Abelian val) const; |
$\min \lbrace\,k \mid \sum_{i = 0}^k A_i \geq \mathrm{val} \rbrace$ | $A_i \geq (\text{単位元})$ ($i = 0,\ldots, N - 1$) |
template <typename Abelian>
struct FenwickTreeSupportingRangeAddQuery;
Abelian
:アーベル群である要素型名前 | 効果・戻り値 |
---|---|
explicit FenwickTreeSupportingRangeAddQuery(const int n_, const Abelian ID = 0); |
要素数 $N$、単位元 $\mathrm{id}$ のオブジェクトを構築する。 |
void add(int left, const int right, const Abelian val); |
$A_i \gets A_i + \mathrm{val}$ ($i = \mathrm{left},\ldots, \mathrm{right} - 1$) |
Abelian sum(const int idx) const; |
$\sum_{i = 0}^{\mathrm{idx} - 1} A_i$ |
Abelian sum(const int left, const int right) const; |
$\sum_{i = \mathrm{left}}^{\mathrm{right} - 1} A_i$ |
Abelian operator[](const int idx) const; |
$A_{\mathrm{idx}}$ |
template <typename Abelian>
struct FenwickTreeSupportingRangeAddQuery;
Abelian
:アーベル群である要素型名前 | 効果・戻り値 |
---|---|
explicit FenwickTree2D(const int height_, const int width_, const Abelian ID = 0); |
要素数 $\mathrm{height} \times \mathrm{width}$、単位元 $\mathrm{id}$ のオブジェクトを構築する。 |
void add(int y, int x, const Abelian val); |
$A_{yx} \gets A_{yx} + \mathrm{val}$ |
Abelian sum(int y, int x) const; |
$\sum_{i = 0}^y \sum_{j = 0}^x A_{ij}$ |
Abelian sum(const int y1, const int x1, const int y2, const int x2) const; |
$\sum_{i = y_1}^{y_2} \sum_{j = x_1}^{x_2} A_{ij}$ |
Abelian get(const int y, const int x) const; |
$A_{yx}$ |
template <typename Abelian>
struct FenwickTree2DSupportingRangeAddQuery;
Abelian
:アーベル群である要素型名前 | 効果・戻り値 |
---|---|
explicit FenwickTree2DSupportingRangeAddQuery(const int height_, const int width_, const Abelian ID = 0); |
要素数 $\mathrm{height} \times \mathrm{width}$、単位元 $\mathrm{id}$ のオブジェクトを構築する。 |
void add(int y1, int x1, int y2, int x2, const Abelian val); |
$A_{ij} \gets A_{ij} + \mathrm{val}$ ($y_1 \leq i \leq y_2,\ x_1 \leq j \leq x_2$) |
Abelian sum(int y, int x) const; |
$\sum_{i = 0}^y \sum_{j = 0}^x A_{ij}$ |
Abelian sum(const int y1, const int x1, const int y2, const int x2) const; |
$\sum_{i = y_1}^{y_2} \sum_{j = x_1}^{x_2} A_{ij}$ |
$A_{ij} \gets A_{ij} + v$ ($y_1 \leq i \leq y_2,\ x_1 \leq j \leq x_2$) を考える。
$S \mathrel{:=} \sum_{i = 1}^y \sum_{j = 1}^x A_{ij}$ とおき、加算前の $S$ を $S_b$、加算後の $S$ を $S_a$ とすると
$y_1 \leq y \leq y_2,\ x_1 \leq x \leq x_2$ のとき
\[\begin{aligned} S_a - S_b &= v(y - y_1 + 1)(x - x_1 + 1) \\ &= vyx - v(x_1 - 1)y - v(y_1 - 1)x + v(y_1 - 1)(x_1 - 1) \end{aligned}\]が成り立つ。$S_1 \mathrel{:=} vyx - v(x_1 - 1)y - v(y_1 - 1)x + v(y_1 - 1)(x_1 - 1)$ とおく。
$y_1 \leq y \leq y_2,\ x_2 < x$ のとき
\[\begin{aligned} S_a - S_b &= v(y - y_1 + 1)(x_2 - x_1 + 1) \\ &= -v(x_1 - 1)y + v(y_1 - 1)(x_1 - 1) + vx_2y - v(y_1 - 1)x_2 \\ &= S_1 - vyx + v(y_1 - 1)x + vx_2y - v(y_1 - 1)x_2 \end{aligned}\]が成り立つ。$S_2 \mathrel{:=} - vyx + v(y_1 - 1)x + vx_2y - v(y_1 - 1)x_2$ とおく。
$y_2 < y,\ x_1 \leq x \leq x_2$ のとき
\[\begin{aligned} S_a - S_b &= v(y_2 - y_1 + 1)(x - x_1 + 1) \\ &= -v(y_1 - 1)x + v(y_1 - 1)(x_1 - 1) + vy_2x - vy_2(x_1 - 1) \\ &= S_1 - vyx + v(x_1 - 1)y + vy_2x - vy_2(x_1 - 1) \end{aligned}\]が成り立つ。$S_3 \mathrel{:=} - vyx + v(x_1 - 1)y + vy_2x - vy_2(x_1 - 1)$ とおく。
$y_2 < y,\ x_2 < x$ のとき
\[\begin{aligned} S_a - S_b &= v(y_2 - y_1 + 1)(x_2 - x_1 + 1) \\ &= v(y_1 - 1)(x_1 - 1) - v(y_1 - 1) x_2 - vy_2(x_1 - 1) + v y_2 x_2 \\ &= S_1 + S_2 + S_3 + vyx - vy_2x - vx_2y + vy_2x_2 \end{aligned}\]が成り立つ。
$\text{otherwise}$
\[S_a - S_b = 0\]が成り立つ。
#ifndef EMTHRM_DATA_STRUCTURE_FENWICK_TREE_2D_FENWICK_TREE_SUPPORTING_RANGE_ADD_QUERY_HPP_
#define EMTHRM_DATA_STRUCTURE_FENWICK_TREE_2D_FENWICK_TREE_SUPPORTING_RANGE_ADD_QUERY_HPP_
#include <vector>
namespace emthrm {
template <typename Abelian>
struct FenwickTree2DSupportingRangeAddQuery {
explicit FenwickTree2DSupportingRangeAddQuery(
const int height_, const int width_, const Abelian ID = 0)
: height(height_ + 1), width(width_ + 1), ID(ID) {
data_const.assign(height, std::vector<Abelian>(width, ID));
data_linear[0].assign(height, std::vector<Abelian>(width, ID));
data_linear[1].assign(height, std::vector<Abelian>(width, ID));
data_quadratic.assign(height, std::vector<Abelian>(width, ID));
}
void add(int y1, int x1, int y2, int x2, const Abelian val) {
++y1; ++x1; ++y2; ++x2;
for (int i = y1; i < height; i += i & -i) {
for (int j = x1; j < width; j += j & -j) {
data_const[i][j] += val * (y1 - 1) * (x1 - 1);
data_linear[0][i][j] -= val * (x1 - 1);
data_linear[1][i][j] -= val * (y1 - 1);
data_quadratic[i][j] += val;
}
}
for (int i = y1; i < height; i += i & -i) {
for (int j = x2 + 1; j < width; j += j & -j) {
data_const[i][j] -= val * (y1 - 1) * x2;
data_linear[0][i][j] += val * x2;
data_linear[1][i][j] += val * (y1 - 1);
data_quadratic[i][j] -= val;
}
}
for (int i = y2 + 1; i < height; i += i & -i) {
for (int j = x1; j < width; j += j & -j) {
data_const[i][j] -= val * y2 * (x1 - 1);
data_linear[0][i][j] += val * (x1 - 1);
data_linear[1][i][j] += val * y2;
data_quadratic[i][j] -= val;
}
}
for (int i = y2 + 1; i < height; i += i & -i) {
for (int j = x2 + 1; j < width; j += j & -j) {
data_const[i][j] += val * y2 * x2;
data_linear[0][i][j] -= val * x2;
data_linear[1][i][j] -= val * y2;
data_quadratic[i][j] += val;
}
}
}
Abelian sum(int y, int x) const {
++y; ++x;
Abelian quad = ID, cons = ID, line[2]{ID, ID};
for (int i = y; i > 0; i -= i & -i) {
for (int j = x; j > 0; j -= j & -j) {
quad += data_quadratic[i][j];
line[0] += data_linear[0][i][j];
line[1] += data_linear[1][i][j];
cons += data_const[i][j];
}
}
return quad * y * x + line[0] * y + line[1] * x + cons;
}
Abelian sum(const int y1, const int x1, const int y2, const int x2) const {
return y1 > y2 || x1 > x2 ? ID : sum(y2, x2) - sum(y2, x1 - 1)
- sum(y1 - 1, x2) + sum(y1 - 1, x1 - 1);
}
private:
const int height, width;
const Abelian ID;
std::vector<std::vector<Abelian>> data_const, data_quadratic;
std::vector<std::vector<Abelian>> data_linear[2];
};
} // namespace emthrm
#endif // EMTHRM_DATA_STRUCTURE_FENWICK_TREE_2D_FENWICK_TREE_SUPPORTING_RANGE_ADD_QUERY_HPP_
#line 1 "include/emthrm/data_structure/fenwick_tree/2d_fenwick_tree_supporting_range_add_query.hpp"
#include <vector>
namespace emthrm {
template <typename Abelian>
struct FenwickTree2DSupportingRangeAddQuery {
explicit FenwickTree2DSupportingRangeAddQuery(
const int height_, const int width_, const Abelian ID = 0)
: height(height_ + 1), width(width_ + 1), ID(ID) {
data_const.assign(height, std::vector<Abelian>(width, ID));
data_linear[0].assign(height, std::vector<Abelian>(width, ID));
data_linear[1].assign(height, std::vector<Abelian>(width, ID));
data_quadratic.assign(height, std::vector<Abelian>(width, ID));
}
void add(int y1, int x1, int y2, int x2, const Abelian val) {
++y1; ++x1; ++y2; ++x2;
for (int i = y1; i < height; i += i & -i) {
for (int j = x1; j < width; j += j & -j) {
data_const[i][j] += val * (y1 - 1) * (x1 - 1);
data_linear[0][i][j] -= val * (x1 - 1);
data_linear[1][i][j] -= val * (y1 - 1);
data_quadratic[i][j] += val;
}
}
for (int i = y1; i < height; i += i & -i) {
for (int j = x2 + 1; j < width; j += j & -j) {
data_const[i][j] -= val * (y1 - 1) * x2;
data_linear[0][i][j] += val * x2;
data_linear[1][i][j] += val * (y1 - 1);
data_quadratic[i][j] -= val;
}
}
for (int i = y2 + 1; i < height; i += i & -i) {
for (int j = x1; j < width; j += j & -j) {
data_const[i][j] -= val * y2 * (x1 - 1);
data_linear[0][i][j] += val * (x1 - 1);
data_linear[1][i][j] += val * y2;
data_quadratic[i][j] -= val;
}
}
for (int i = y2 + 1; i < height; i += i & -i) {
for (int j = x2 + 1; j < width; j += j & -j) {
data_const[i][j] += val * y2 * x2;
data_linear[0][i][j] -= val * x2;
data_linear[1][i][j] -= val * y2;
data_quadratic[i][j] += val;
}
}
}
Abelian sum(int y, int x) const {
++y; ++x;
Abelian quad = ID, cons = ID, line[2]{ID, ID};
for (int i = y; i > 0; i -= i & -i) {
for (int j = x; j > 0; j -= j & -j) {
quad += data_quadratic[i][j];
line[0] += data_linear[0][i][j];
line[1] += data_linear[1][i][j];
cons += data_const[i][j];
}
}
return quad * y * x + line[0] * y + line[1] * x + cons;
}
Abelian sum(const int y1, const int x1, const int y2, const int x2) const {
return y1 > y2 || x1 > x2 ? ID : sum(y2, x2) - sum(y2, x1 - 1)
- sum(y1 - 1, x2) + sum(y1 - 1, x1 - 1);
}
private:
const int height, width;
const Abelian ID;
std::vector<std::vector<Abelian>> data_const, data_quadratic;
std::vector<std::vector<Abelian>> data_linear[2];
};
} // namespace emthrm