ACL｜通用「树状数组」模板
2024-11-04 14:01:49
发布于：浙江
前言
像使用
std::vector一样，使用「树状数组」。
本文将介绍 AC(AtCoder) Library 中提供的 fenwick_tree 模版。
本文最后提供的 FenwickTree.cpp 对源码进行了一定的修改使得其可以单独在每一份 cpp 代码中使用。
树状数组简单来说即为支持在线求前缀和的一种特殊数据结构（请把复杂的功能交给「线段树」）。
使用树状数组，不需要知道树状数组的原理！
当你需要一边「修改数组中单个元素」，又同时需要查询数组的「前缀和」时，那么不要犹豫，把此模版粘贴你的代码中去吧！
然后就可以像使用 中的 std::vector，std::map 等容器一样使用「树状数组」啦！
示例
以下为使用 FenwickTree 和 Modint 后，挑战赛#10 的第 6 题，Ptorrweee 最后统计答案部分的代码。
using mint = Modint<998244353>;
FenwickTree<mint> ft(n + 1);
for (int i = 0; i < q; ++i) {
int t, u;
std::cin >> t >> u; --u;
if (t == 1) {
int x; std::cin >> x;
mint s = mint(a).pow(x - dep[u]);
ft.add(dfn[u], s);
ft.add(dfn[u] + sz[u], -s);
}
else
std::cout << (ft.sum(0, dfn[u] + 1) * mint(a).pow(dep[u])).val() << '\n';
}
可以看出，结合使用两个算法模板后，可以将最后的代码变得十分简洁。将「树状数组」封装，特别在题目需要有多个树状数组求解时尤其方便。
操作
1. 构造函数
FenwickTree<T> ft(int n)
- 定义一个长度为 的数组 。所有元素被初始化为 。
注意 T 的类型为 int，long long，unsigned，unsigned long long 或 Modint 类型。
且 ；构造函数的时间复杂度为 。
2. add
void fw.add(int p, T x)
- 执行
a[p] += x操作。
要求 ；时间复杂度 。
3. sum
(1) T fw.sum(int l, int r)
(2) T fw.sum(int r)
- 该方法返回 的和。
- 该方法返回 的和。
以上方法要求 ；时间复杂度皆为 。
FenwickTree.cpp
template<class T>
class FenwickTree {
private: // fenwickTree for interval [0, n)
int n;
std::vector<T> data;
public:
FenwickTree() : FenwickTree(0) {}
explicit FenwickTree(int n) : n(n), data(n) {}
void add(int p, T x) {
assert(0 <= p and p < n);
p += 1;
while (p <= n) {
data[p - 1] += x;
p += p & -p;
}
}
T sum(int l, int r) {// return sum of [l, r)
assert(0 <= l and l <= r and r <= n);
return sum(r) - sum(l);
}
T sum(int r) {// return sum of [0, r)
assert(0 <= r and r <= n);
T s = 0;
while (r > 0) {
s += data[r - 1];
r -= r & -r;
}
return s;
}
};
全部评论 10
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
2024-10-20 来自 上海
011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
2024-10-20 来自 上海
011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
2024-10-20 来自 上海
0
有帮助，赞一个