出处1 出处2

假设树状数组是 $bit[N]$，$bit[i]$ 表示 $i-LSB(i)+1$ 到 $i$ 这个区间的和

询问

根据定义，$bit[i]$ 已经包含 $i-LSB(i)+1$ 到 $i$ 这个区间了，所以在$i>0$的时候不断 $ret\leftarrow ret+bit[i], i\leftarrow i-LSB(i)$ 就可以求所要的前缀和了

而对于$i>0$显然有 $i-LSB(i)<i$，于是这个过程一定可以终止

更新

比如修改 $a[p]$，显然 $bit[p]$ 需要更新，接下来证明要更新的是 $bit[p+LSB(p)]$，$bit[p+LSB(p)+LSB(p+LSB(p))]$ 之类的

分两步

第一步：证明 $ bit[p] $ 真包含于 $ bit[p+LSB(p)] $

设$p=s \times 2^{k+1} + 2^k$（显然任意整数$p$都能写成这个形式），则$LSB(p)=2^k$，$p+LSB(p)=(s+1) \times 2^{k+1}$

不难发现 $LSB(u) \ge 2^{k+1}$，其中 $u=p+LSB(p)$ ，由此得出

$ u-LSB(u)+1 \le u-2^{k+1}+1 = s \times 2^{k+1} + 1 = p-LSB(p)+1 \le p < p+LSB(p) $

第二部：证明对任意满足 $ p<i<p+LSB(p) $ 的 $ i $ ， $ bit[i] $ 不包含 $ bit[p] $

设$p=s \times 2^{k+1} + 2^k$，则$i=s \times 2^{k+1}+2^k+b$，其中$1 \le b < 2^k$

不难发现 $LSB(i)=LSB(b)$

从而 $i-LSB(i)+1=i-LSB(b)+1 \geq i-b+1 = p+1 > p$ 即$bit[i]$不包含$bit[p]$

所以在$i \le n$时不断 $bit[i] \leftarrow bit[i] + delta, i\leftarrow i+LSB(i)$，显然这个过程也一定会终止