树状数组

学习数据结构与算法
2021-05-17 14:29 · 阅读时长4分钟
小课

树状数组和线段树一样,也是用来维护区间信息的,不过实现起来比线段树更加简洁,但是没有线段树灵活、强大。树状数组,很明显就是说数组的逻辑结构是树形的,但是这个树形数组和之前提到过的结构都不太一样,它的子节点和父节点的位置并不是2n,2n+1,2n+2等这种关系,而是通过一个特殊的函数lowbit来获取,lowbit函数实际功能是取当前数字二进制形式从右往左直到遇到1为止所表示的值,比如说十进制6,它的二进制表示为110,lowbit要取的值就是10,也就是2。它可以通过以下方式实现

public int lowBit(int val) {
    return val & -val;
}

并且在查询、和更新树状数组时,使用方式还不一样,在更新时,通过parent = child + lowbit(child) 来获取父节点的位置,而在查询时,通过parent = child - lowbit(child)来获取父节点位置。

下面以数组arr=[1, 2, 3, 4, 5, 6, 7, 8]求区间和为例,看看具体这个树状数组是什么样的。

树状数组

树状数组实现起来比较简单,主要是理解更新和查询时树的结构。

加载中...

一般来说,能用树状数组来实现,就用树状数组来实现,因为树状数组实现简单,而且效率要比线段树高一些。

树状数组Fenwick TreeBinary Indexed Tree