2023-01-08-树状数组BIT正确性的证明
出处1 出处2
假设树状数组是 ， 表示 到 这个区间的和
根据定义， 已经包含 到 这个区间了，所以在的时候不断 就可以求所要的前缀和了
而对于显然有 ，于是这个过程一定可以终止
比如修改 ，显然 需要更新，接下来证明要更新的是 ， 之类的
分两步
设（显然任意整数都能写成这个形式），则，
不难发现 ，其中 ，由此得出
设，则，其中
不难发现
从而 即 不包含
所以在时不断 ，显然这个过程也一定会终止
第一步：证明 真包含于
第二部：证明对任意满足 的 ， 不包含