线段树和树状数组之间的联系

缘起

突有所悟~ 遂写下此随笔~ 菊苣莫笑哈~

分析

返璞归真~ 树状数组伊始是想解决什么问题的?

给定一个初始序列. a1,...,an, 序列允许如下操作
(i,x)表示a[i]+=x
询问 a[s,..,t]的片段和.

首先, 想要求片段和, 我们只需求出部分和即可, 即 Sn, 一旦求出部分和序列, 则片段和可以在O(1)时间得到. 而如果使用线段树怎么得到部分和?

不就是用索引范围 [1,n] 在O(nlogn)时间内建立一棵线段树, 然后遍历a[1,..,n]插入线段树, 线段树的节点维护一下该节点代表的数组a的索引范围a[beign,…,end]的片段和即可（即节点的sum域）. 总时间是O(nlogn). 现在进行 (i,x)操作. 则可以从线段树根节点入手, 找到相应的叶子节点. 而这一路上, 修改O(logn)个节点的sum域即可. 单点修改耗时O(logn). 一旦要回答询问的话, 不仅仅是[1,i] 这种部分和询问, 即便是一般的片段和[s,t] 也能在 O(log|s-t|)时间内完成. 这就是线段树对于上面提出的问题的解答.

ps: 其实如果做过【1】的话, 就知道, 线段树不仅仅支持单点修改, 对于区间修改也是可以做的. 但是本文就是仅仅讨论单点修改.

那么, 怎么自然的演进到树状数组呢?

首先, 我们对于线段树解法画出如下的线段树.其次, 对于求Si=a1+…+ai 部分和, 下面的划了斜线的节点是不需要的（你将[1,i]这样的区间压入线段树的根节点, [1,i]被不断的二分, 但是在线段树代码中真正能return掉的节点仅仅是下图中没有划线的节点）.

好的，我们将划线的节点从线段树中去掉

好的, 我告诉你, 去掉划线节点之后的数据结构就是树状数组（BIT）. 即线段树中只需要保留树状数组中的如上节点就足以解决S[1,…,i]求和和(i,x)更新操作了.

所以就不难理解树状数组能做的事情, 线段树一定能做. 但是反之不对——他俩并不是等价的数据结构——因为很明显的, 线段树信息可以推出树状数组的信息，反之显然不对.

那么不难理解树状数组的求和和（单点）更新操作了. 对于求和, 例如S6，6的lowbit是2, 所以就是下图A和B两个子节点的和

而A就是6-2（6的lowbit）.

而树状数组的更新也是很好理解的. 例如进行了单点操作 (i,x), 例如a[3]+=1这样的操作. 而3能影响的树状数组中的节点是3+1（3的lowbit）=4， 4+4（4的lowbit）=8（注意, 加上lowbit其实就是向前一倍的长度）

参考

【1】https://yfsyfs.github.io/2019/07/13/%E7%BA%BF%E6%AE%B5%E6%A0%91-fzu-2171-%E9%98%B2%E5%AE%88%E9%98%B5%E5%9C%B0-II/