前言
写这玩意的时候我突发奇想写了个线段树交了模板题，然后 RE\color{purple}RERE 了。
这件事情告诉我们 xds 有风险，摇轮椅需谨慎。
本文遵循了洛谷和 ACGO 的格式手册。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正文
什么是树状数组？
树状数组可以实现带修改的区间查询操作。
注意到这个操作可以由线段树实现，但是正如上面所说线段树容易让你受到
Received signal 11: Segmentation fault with invalid memory reference.
的诅咒，所以还是树状数组好使。同时，树状数组的空间占用低于线段树。
讲解树状数组
> 这段的图片回去会重做的。
首先这个是一个随机（？）序列（最下面是下标）：
我们要对这个序列建树状数组。为此，我们两两合并：
然后，我们注意到：
* 求下标 111 的前缀和需要下标 111 位置上的 111；
* 求下标 222 的前缀和需要下标 222 位置上的 101010；
* 求下标 333 的前缀和需要下标 222 位置上的 101010，下标 333 位置上的 111；
* ⋯\cdots⋯ ⋯\cdots⋯
显然只有这些是需要的（最下面保留了一层原数组，用横线表示了管辖范围）：
你稍微观察就可以发现，每一个下标只有一个对应的数字，因此得到数组 ttt ：
这就是树状数组。
然后我们要实现两个操作：前缀和查询和单点修改。
修改
先把上面扒来：
比如说我们要把下标为 333 的元素增加 555 。
区间修改的思路如下：
首先我们需要知道，具体要对树状数组的哪些元素进行修改。
看图我们发现，需要修改下标为 333 , 444 , 888 的元素。
然后我们发现：
(3)10=(11)2(4)10=(100)2(8)10=(1000)2(3)_{10}=(11)_2\\ (4)_{10}=(100)_2\\ (8)_{10}=(1000)_2 (3)10 =(11)2 (4)10 =(100)2 (8)10 =(1000)2
然后继续运用惊人的注意力，得到：
4=3+lowbit(3)8=4+lowbit(4)4=3+lowbit(3)\\ 8=4+lowbit(4) 4=3+lowbit(3)8=4+lowbit(4)
然后我们就可以得到区间修改的思路：
将当前下标 xxx 加上修改的数，然后将 xxx 加上 lowbit(x)lowbit(x)lowbit(x)。
具体证明详见 OI - Wiki，或者也许哪天我会把证明搬过来？（其实我在 Wiki 也没有找到单独的证明，大概是有依据的）
前缀和查询
还是这个数组。
现在，我们查询下标为 777 的元素的前缀和。
观察管辖区间：
我们会用到树状数组中下标为 444，666，777 的元素。
根据上面的经验，我们再次转换为二进制：
(4)10=(100)2(6)10=(110)2(7)10=(111)2(4)_{10}=(100)_2\\ (6)_{10}=(110)_2\\ (7)_{10}=(111)_2 (4)10 =(100)2 (6)10 =(110)2 (7)10 =(111)2
然后继续注意。
6=7−lowbit(7)4=6−lowbit(6)6=7-lowbit(7)\\ 4=6-lowbit(6) 6=7−lowbit(7)4=6−lowbit(6)
得到：
将当前答案加上树状数组下标为 xxx 的数，然后将 xxx 减去 lowbit(x)lowbit(x)lowbit(x)。
建树
首先我们注意到初始的树状数组每一元素都是 000，可以看作对一个全是 000 的数组建立的树状数组。
然后对于有值的数组建立树状数组，我们可以看作在对所有元素为 000 建立的树状数组的基础上，对于每一元素加上对应的原数组的值。
完整模板
例题
P3374 【模板】树状数组 1 / A22721.【模板】树状数组 1
纯模板，我们直接丢一个模板然后浇上浓浓的汁输入输出。
注意到区间的查询和正常前缀和的查询近似。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
下期预告
树状数组的区间修改和单点查询。
---全文完---
