树状数组的性质

树状数组与其树形态的性质

我们约定

• $l(x)=x-lowbit(x)+1$。即 $l(x)$ 是 $c[x]$ 管辖范围的左端点。
• 对于任意正整数 $x$，总能将 $x$ 表示为 $s\times 2^{k+1}+2^k$，其中 $lowbit(x)=2^k$。
• $c[x]$ 与 $c[y]$ 不交，指的是 $c[x]$ 的管辖范围和 $c[y]$ 的管辖范围不相交，即 $[l(x),x]$ 和 $[l(y),y]$ 不相交。

性质1

对于 $x\le y$，要么有 $c[x]$ 和 $c[y]$ 不交，要么有 $c[x]$ 包含于 $c[y]$。

证明

不妨假设 $c[x]$ 与 $c[y]$ 相交，即 $[l(x),x]$ 与 $[l(y),y]$，则一定有 $l(y)\le x\le y$。

又因为 $y=s\times 2^{k+1}+2^k$，故 $l(y)=y-lowbit(y)+1=s\times 2^{k+1}+1$ 。

又因为 $x\ge l(y)$，所以 $x=s\times 2^{k+1}+b$，故 $lowbit(x)=lowbit(b)$。

因为 $b\ge lowbit(b)$，所以 $l(x)=x-low(b)+1=s\times 2^{k+1}+b-lowbit(b)+1$。

所以 $l(x)=l(y)+b-lowbit(b)\ge l(y)$。

所以 $l(x)$ 在 $l(y)$ 的右边，则有不等式：$l(y)\le l(x)\le x\le y$。

故如果 $c[x]$ 与 $c[y]$ 相交，则 $c[x]$ 包含与 $c[y]$。

性质2

$c[x]$ 真包含于 $c[x+lowbit(x)]$。

证明

不妨假设 $y=x+lowbit(x)$。设 $x=s\times 2^{k+1}+2^k$，则 $lowbit(x)=2^k$，故 $y=s\times 2^{k+1}+2^{k+1}$。

若 $s$ 为奇数，则 $y=\frac{(s+1)}{2}\times 2^{k+2}(t\ge 1)$，故 $lowbit(y)=2^{k+2}$，若 $s$ 为偶数，则 $lowbit(y)=2^{k+1}$。

当 $s$ 为奇数，此时 $l(y)=y-lowbit(y)+1=\frac{(s-1)}{2}{2}^{k+2}+1=(s-1)\times 2^{k+1}+1$，

$l(x)=s\times 2^{k+1}+1$，显然有 $l(y)<l(x)\le x<y$，即 $c[x]$ 真包含于 $c[x+lowbit(x)]$。

当 $s$ 为偶数，此时 $l(y)=y-lowbit(y)+1=(s-1)\times 2^{k+1}+1$，显然有 $l(y)<l(x)<x<y$，即 $c[x]$ 真包含于 $c[x+lowbit(x)]$。

性质3

对于任意 $x<y<x+lowbit(x)$，有 $c[x]$ 和 $c[y]$ 不交。

证明

设 $x=s\times 2^{k+1}+2^k$，$y=s\times 2^{k+1}+2^k+b=(2s+1)\times 2^k+b$，

则 $lowbit(x)=2^k,lowbit(y)=lowbit(b)$。

此时 $l(x)=s\times 2^{k+1}+1$，$l(y)=x+b-lowbit(b)+1$。

不难发现有 $l(y)>x$，所以 $c[x]$ 和 $c[y]$ 不交。

根据这三个性质，我们可以得到一个推论。

推论

如果 $tree[i+x]$ 能够管辖到 $i$，那么从 $i$ 开始一直加 $lowbit(i)$ 必然能够到达 $i+x$。

证明

首先所有的 $i$ 跳 $lowbit$ 能到达的位置，都能管辖到 $i$。

又因为 $tree[i+x]$ 能管辖到 $i$，且不能被 $i$ 跳到，说明 $tree[i+x]$ 是在 $i$ 的两个相邻祖先的中间。

又由性质 $3$，对于任意 $x<y<x+lowbit(x)$，有 $c[x]$ 和 $c[y]$ 不交。

说明 $i+x$ 必然不与 $i$ 的祖先有交集，但是 $i+x$ 与 $i$ 的任意祖先都至少交于 $i$，所以矛盾。

故 $i+x$ 必然是 $i$ 的某个祖先，所以所有能管辖到 $i$ 的位置都是 $i$ 的祖先。