10
前言
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 像使用 std::vector 一样，使用「树状数组」。
本文将介绍 AC(AtCoder) Library 中提供的 fenwick_tree 模版。
本文最后提供的 FenwickTree.cpp 对源码进行了一定的修改使得其可以单独在每一份 cpp 代码中使用。
树状数组简单来说即为支持在线求前缀和的一种特殊数据结构（请把复杂的功能交给「线段树」）。
使用树状数组，不需要知道树状数组的原理！
当你需要一边「修改数组中单个元素」，又同时需要查询数组的「前缀和」时，那么不要犹豫，把此模版粘贴你的代码中去吧！
然后就可以像使用 STL\tt{STL}STL 中的 std::vector，std::map 等容器一样使用「树状数组」啦！
示例
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
以下为使用 FenwickTree 和 Modint 后，挑战赛#10 的第 6 题，Ptorrweee 最后统计答案部分的代码。
可以看出，结合使用两个算法模板后，可以将最后的代码变得十分简洁。将「树状数组」封装，特别在题目需要有多个树状数组求解时尤其方便。
操作
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 构造函数
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
* 定义一个长度为 nnn 的数组 a0,a1,⋯ ,an−1a_0, a_1, \cdots, a_{n - 1}a0 ,a1 ,⋯,an−1 。所有元素被初始化为 000。
注意 T 的类型为 int，long long，unsigned，unsigned long long 或 Modint 类型。
且 0≤n≤1080 \le n \le 10^80≤n≤108；构造函数的时间复杂度为 O(n)\mathrm{O(n)}O(n)。
2. ADD
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
* 执行 a[p] += x 操作。
要求 0≤p<n0 \le p \lt n0≤p<n；时间复杂度 O(logn)\mathrm{O(\log{n})}O(logn)。
3. SUM
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 该方法返回 al,al+1,⋯ ,ar−1a_l, a_{l + 1}, \cdots, a_{r - 1}al ,al+1 ,⋯,ar−1 的和。
2. 该方法返回 a0,a1,⋯ ,ar−1a_0, a_{1}, \cdots, a_{r - 1}a0 ,a1 ,⋯,ar−1 的和。
以上方法要求 0≤l≤r≤n0 \le l \le r \le n0≤l≤r≤n；时间复杂度皆为 O(logn)\mathrm{O(\log{n})}O(logn)。
FENWICKTREE.CPP
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
有帮助，赞一个