原文在此，注意作者就是我，放在这里当然是为了防止你们怀疑我（虽然我并不确定你们会怀疑什么）

树状数组的构造过程是这样的： 对于一段序列 $A[1\dots{}n]$，把所有奇数项偶数项分开得到数组 $P$ $Q$，偶数项每项加上其左边的奇数项得到 $P + Q$，偶数项求一遍树状数组得到 $T(P + Q)$，最后把 $P$ 和 $T(P + Q)$ 交替排列出来。

举例：

$$\begin{array}{|c|c|c|c|c|l|} \hline 1&3&5&6&8&原数组\\\hline &3&&6&&分离偶数项\\\hline &4&&11&&每个偶数项加上其左边的奇数项\\\hline &4&&15&&递归求树状数组\\\hline 1&4&5&15&8&把奇数项交替排列回去\\\hline \end{array}$$

树状数组，一个数 $n$ 能当偶数项 $k$ 次，进入 $k$ 次递归中，那么 $n$ 的二进制最后有 $k$ 个 $0$，因为每“当”一次偶数项，它所管辖的区间就会加倍，所以它的值就是原数组里以 $n$ 结尾长度为 $2^k$ 的一段区间。注意到 $lowbit(n) = 2^k$。如果区间写成左开右闭的，那么树状数组里第 $n$ 项就是原数组 $(n - lowbit(n), n]$ 的和。

举例。要查询前 $10$ 个数的前缀和，二进制是 $(1010)_2$，我们可以将其拆成如下两个区间：$(8, 10]$ 和 $(0, 8]$。

修改的话，观察构造树状数组的过程，观察原数组的某下标上如果被加上了一个变化量 $d$，那么这个 $d$ 会怎样传播。

在某一层，如果这个下标 $n$ 是偶数项，那么它左边的奇数项被加过来，这两项原本应该是 $a$ 和 $a + b$ 的，变成了 $a$ 和 $a + b + d$，恰好就是第 n 位被改了；但是如果是奇数项的话，$a$ 和 $a + b$ 要变成 $a + d$ 和 $a + d + b$，也就是说 $d$ 被传播到了 $n$ 右边的偶数项。当然影响是要传递的。

所以我们修改的下标 $n$ 在某一层作为奇数项的时候，它影响到了它在这一层右边的偶数项 $n'$，$n'$ 又会影响到 $n''$，以此类推。

举例：$10$ 在第 $2$ 层的时候，它在这层的编号是 $5$，很不幸地影响到了这层编号是 $6$，即原编号 $12$ 的元素。

我们来看一下二进制表示。$10 = (1010)_2$ 在第 $2$ 层是 $5 = (101)_2$，影响到的是 $5 + 1 = 6 = (110)_2$。（此处感谢 UOJ 用户 rabbit_lb 提醒修改）在第 $2$ 层，加的这个 $1$，应该对应原数组上的 $1 \times 2^1 = 2$，就是 $lowbit(10)$！

这是为什么呢？因为一个二进制最后有 $k$ 个 $0$ 的下标 $n$ 会在第 $k + 1$ 层，作为 $n \over 2^k$ 影响到 $1 + {n \over 2^k}$，在原数组上的下标就是 $n$ 影响到 $2^k + n = lowbit(n) + n$。

当然影响是要传递的，所以修改的时候就是不停加 $lowbit$ 改就行了

（敲 $ 敲到手抽筋。。。）

（然后还发现一个神奇的事情

\begin{array}
1&2&3\\
4&5&6
\end{array}

\begin{array} 1&2&3\\ 4&5&6 \end{array}

论不好好记 TeX 命令用法的坏处）