如何从基础掌握树状数组，达到令人费解的运用境界？

本文共计4022个文字，预计阅读时间需要17分钟。

一维树状数组基本原理+参考OI-wiki上的图用：原理是对每个节点，存储一段连续长度的区间，表示为(2^k)的次方区间。具体来说，对于数x，其管理长度为lowbit(x)的区间。

一维树状数组 树状数组基本原理

我们借 OI-wiki 上的图用用:

原理是对于每个节点，存储一段连续的长度为 \(2\) 的次幂的区间。

而具体来说，对于一个数 \(x\) ，其管理 \(lowbit(x)\) 长度的区间，而这具体是那个区间也可以写出: \((x-lowbit(x),x]\)。

然后还有一些性质：

性质1：

对于一个节点 \(x\) 来说 \(x+lowbit(x)\) 为其父节点。

证明：

简单证一下，发现 \(x+lowbit(x)\) 实际上是将 \(x\) 的最低位抹除了，并且往高位进位。然后直接进入到最近的满的整幂次位，树形意义上就是进入父亲。

Q.E.D.

lowbit

然后我们看如何快速求得 \(lowbit\) 。

其实很好做， \(lowbit(x)=x\&-x\)。这是为什么？

实际上是利用了补码：负数的反码是原码符号位不动，其他位按位取反。补码是在其反码的基础上 \(+1\) ，那么它会连续进位直到遇到第一个 \(1\) 。高位和原来完全不同，因此有 \(x\&-x\) 为 \(lowbit\) 。

单点修改区间查询

最经典的树状数组。需要注意的是树状数组可以存储的信息需要有区间可减性或者只需要查询从 \(1\) 开始的，否则不能用树状数组。因为其区间查询是通过两次前缀查询做差分得到的。

单点修改简单，只需要先找到要修改的位置，然后直接跳父亲修改即可。修改的位置就是其本身。注意下标不能开到 \(0\)，应该说不能对 \(0\) 位置进行修改操作，不然会死循环。可以通过下标整体 \(+1\) 之类的操作解决。

区间查询稍微复杂一些。

我们将查询的前缀分为若干段。具体来说，我们把前缀用尽可能大的树状数组上的区间覆盖。