模板
单点修改的树状数组
template<typename T>
struct fenwick_tree {
std::vector<T> ft;
size_t size;
fenwick_tree() = default;
fenwick_tree(size_t n)
: ft(n + 1, 0), size(n) {}
void modify(int pos, T value) {
for (; pos <= size; pos += (pos & (-pos))) {
ft[pos] += value;
}
}
T query(int pos) {
T res = 0;
for (; pos >= 1; pos -= (pos & (-pos))) {
res += ft[pos];
}
return res;
}
T query(int left, int right) {
return query(right) - query(left - 1);
}
};
初始化
fenwick_tree<int> ft(n) 构造类型为 int ，范围为 \([0, n]\) 的树状数组。
单点修改
modify(pos, value)， pos 修改的点的下标， value 修改的 + 值。
查询
query(left, right), 查询范围\([left, right]\), 单点也是范围。
区间修改的树状数组
template<typename T>
struct fenwick_tree {
std::vector<T> ft1, ft2;
size_t size;
fenwick_tree() = default;
fenwick_tree(size_t n)
: ft1(n + 1, 0), ft2(n + 1, 0), size(n) {}
void modify(int pos, T value) {
for (T value2 = value * pos; pos <= size; pos += (pos & (-pos))) {
ft1[pos] += value;
ft2[pos] += value2;
}
}
T query(std::vector<T>& ft, int pos) {
T res = 0;
for (; pos >= 1; pos -= (pos & (-pos))) {
res += ft[pos];
}
return res;
}
void modify(int left, int right, T value) {
modify(left, value);
modify(right + 1, -value);
}
T query(int left, int right) {
return ((1LL + right) * query(ft1, right) - (1LL * left * query(ft1, left - 1)))
- (query(ft2, right) - query(ft2, left - 1));
}
};
初始化
fenwick_tree<int> ft(n) 构造类型为 int ，范围为 \([0, n]\) 的树状数组。
修改
modify(left, right, value)， 修改范围为 \([left, right]\)， value 修改的 + 值。
查询
query(left, right), 查询范围\([left, right]\), 单点也是范围。
单点修改的二维树状数组
template<typename T>
struct fenwick2_tree {
struct vector2 {
std::vector<T> arr;
size_t row, col, size;
vector2() = default;
vector2(size_t n, size_t m)
: arr((n + 1) * (m + 1) + 1, 0), row(n), col(m), size(n * m) {};
T& at(int n, int m) {
if (row < n || col < m) return arr[0];
return arr[n * (col + 1) + m];
}
} ft;
size_t row, col, size;
fenwick2_tree() = default;
fenwick2_tree(size_t n, size_t m)
: ft(n, m), row(n), col(m), size(n * m) {}
void modify(int r, int c, T value) {
for (int i = r; i <= row; i += (i & (-i))) {
for (int j = c; j <= col; j += (j & (-j))) {
ft.at(i, j) += value;
}
}
}
T query(int r, int c) {
T res = 0;
for (int i = r; i >= 1; i -= (i & (-i))) {
for (int j = c; j >= 1; j -= (j & (-j))) {
res += ft.at(i, j);
}
}
return res;
}
T query(int r1, int c1, int r2, int c2) {
return query(r2, c2) -
query(r2, c1 - 1) -
query(r1 - 1, c2) +
query(r1 - 1, c1 - 1);
}
};
初始化
fenwick2_tree<int> ft(n, m) 构造类型为 int ，范围为 \(n \times m\) 的树状数组。
单点修改
modify(r, c, value)， 修改下标 \((r, c)\) 的值， value 修改的 + 值。
查询
query(r1, c1, r2, c2), 查询左上角坐标为 \((r1, c1)\), 右下角坐标为 \((r2, c2)\) 的矩阵的和, 单点也是矩阵。
区间修改, 单点查询的二维树状数组
template<typename T>
struct fenwick2_tree {
struct vector2 {
std::vector<T> arr;
size_t row, col, size;
vector2() = default;
vector2(size_t n, size_t m)
: arr((n + 1) * (m + 1) + 1, 0), row(n), col(m), size(n * m) {};
T &at(int n, int m) {
if (row < n || col < m)
return arr[0];
return arr[n * (col + 1) + m];
}
} ft;
size_t row, col, size;
fenwick2_tree() = default;
fenwick2_tree(size_t n, size_t m)
: ft(n, m), row(n), col(m), size(n * m) {}
void modify(int r, int c, T value) {
for (int i = r; i <= row; i += (i & (-i))) {
for (int j = c; j <= col; j += (j & (-j))) {
ft.at(i, j) += value;
}
}
}
T query(int r, int c) {
T res = 0;
for (int i = r; i >= 1; i -= (i & (-i))) {
for (int j = c; j >= 1; j -= (j & (-j))) {
res += ft.at(i, j);
}
}
return res;
}
void modify(int r1, int c1, int r2, int c2, T value) {
modify(r1, c1, value);
modify(r1, c2 + 1, -value);
modify(r2 + 1, c1, -value);
modify(r2 + 1, c2 + 1, value);
}
};
初始化
fenwick2_tree<int> ft(n, m) 构造类型为 int ，范围为 \(n \times m\) 的树状数组。
修改
modify(r1, c1, r2, c2, value)， 修改左上角坐标为 \((r1, c1)\), 右下角坐标为 \((r2, c2)\) 的矩阵中每个位置的值， value 修改的 + 值。
查询
query(r, c), 查询单点 \((r, c)\) 的值。
区间修改, 区间查询的二维树状数组
template<typename T>
struct fenwick2_tree {
struct vector2 {
std::vector<T> arr;
size_t row, col, size;
vector2() = default;
vector2(size_t n, size_t m)
: arr((n + 1) * (m + 1) + 1, 0), row(n), col(m), size(n * m) {};
T& at(int n, int m) {
if (row < n || col < m) return arr[0];
return arr[n * (col + 1) + m];
}
} ft1, ft2, ft3, ft4;
size_t row, col, size;
fenwick2_tree() = default;
fenwick2_tree(size_t n, size_t m)
: ft1(n, m), ft2(n, m), ft3(n, m), ft4(n, m),
row(n), col(m), size(n * m) {}
void modify(int r, int c, T value) {
for (int i = r; i <= row; i += (i & (-i))) {
for (int j = c; j <= col; j += (j & (-j))) {
ft1.at(i, j) += value;
ft2.at(i, j) += 1LL * (r - 1) * value;
ft3.at(i, j) += 1LL * (c - 1) * value;
ft4.at(i, j) += 1LL * (r - 1) * (c - 1) * value;
}
}
}
T query(int r, int c) {
T res = 0;
for (int i = r; i >= 1; i -= (i & (-i))) {
for (int j = c; j >= 1; j -= (j & (-j))) {
res += 1LL * r * c * ft1.at(i, j) -
c * ft2.at(i, j) -
r * ft3.at(i, j) +
ft4.at(i, j);
}
}
return res;
}
void modify(int r1, int c1, int r2, int c2, T value) {
modify(r1, c1, value);
modify(r1, c2 + 1, -value);
modify(r2 + 1, c1, -value);
modify(r2 + 1, c2 + 1, value);
}
T query(int r1, int c1, int r2, int c2) {
return query(r2, c2) -
query(r2, c1 - 1) -
query(r1 - 1, c2) +
query(r1 - 1, c1 - 1);
}
};
初始化
fenwick2_tree<int> ft(n, m) 构造类型为 int ，范围为 \(n \times m\) 的树状数组。
修改
modify(r1, c1, r2, c2, value)， 修改左上角坐标为 \((r1, c1)\), 右下角坐标为 \((r2, c2)\) 的矩阵中每个位置的值， value 修改的 + 值。
查询
query(r1, c1, r2, c2), 查询左上角坐标为 \((r1, c1)\), 右下角坐标为 \((r2, c2)\) 的矩阵的和, 单点也是矩阵。
