树状数组和下面的线段树可是亲兄弟了，但他俩毕竟还有一些区别：
树状数组能有的操作，线段树一定有；
线段树有的操作，树状数组不一定有。
这么看来选择线段树不就 「得天下了」 ？
事实上，树状数组的代码要比线段树短得多，思维也更清晰，在解决一些单点修改的问题时，树状数组是不二之选。
如果要具体了解树状数组的工作原理，请看下面这张图：
最下面的八个方块就代表存入 中的八个数，现在都是十进制。
他们上面的参差不齐的剩下的方块就代表 的上级—— 数组。
很显然看出：
管理的是 & ；
管理的是 & & & ；
管理的是 & ； 则管理全部 个数。
所以，如果你要算区间和的话，比如说要算 ~ 的区间和，暴力算当然可以，那上百万的数，那就 RE 喽。
那么这种类似于跳一跳的连续跳到中心点而分值不断变大的原理是一样的（倍增）。
你从 开始往前跳，发现 （ 我也不确定是多少，算起来太麻烦，就意思一下）只管 这个点，那么你就会找 ，发现 管的是 & ；那么你就会直接跳到 ， 就会管 ~ 这些数，下次查询从 往前找，以此类推。
那么问题来了，你是怎么知道 管的 的个数分别是多少呢？你那个 个， 个， 个……是怎么来的呢？ 这时，我们引入一个函数—— ：
的意思注释说明了，咱们就用这个说法来证明一下 ：
发现第一个 以及他后面的 组成的二进制是
对应的十进制是 ，所以 一共管理 个 。
这就是 的用处，仅此而已（但也相当有用）。
你可能又问了：x & -x 是什么意思啊？
代表 的负数，计算机中负数使用对应的正数的补码来表示。
例如 :
；
；
。
神奇吧，我也觉得神奇！
那么对于 单点修改 就更轻松了：
每次只要在他的上级那里更新就行，自己就可以不用管了。
若维护序列 的差分数组 ，此时我们对 的一个前缀 求和，即 ，由差分数组定义得
进行推导
区间和可以用两个前缀和相减得到，因此只需要用两个树状数组分别维护 和 ，就能实现区间求和。
代码如下
树状数组还有一些 trick，如 建树、 查询第 小/大元素等，下附代码。
- 树状数组 1：单点修改，区间查询
- 树状数组 2：区间修改，单点查询
- 树状数组 3：区间修改，区间查询
- 二维树状数组 1：单点修改，区间查询
- 二维树状数组 3：区间修改，区间查询
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/12979.html