树状数组理解

Big_fat_cat 发布于2019-08-15 14:20 / 965人阅读

摘要：无意间看到树状数组，查了很多资料被各种图和公式绕晕了，下面记录一点个人理解。

无意间看到树状数组，查了很多资料被各种图和公式绕晕了，下面记录一点个人理解。

假设数组a[0],a[1],a[2],.....,a[n]，记0-m元素之和为sum(m) (0=

遍历累加0-m 时间复杂度O(m)，空间复杂度O(1)

增加辅助数组s[0],s[1],s[2],.....,s[n] 时间复杂度O(1)，空间复杂度O(n)

当我们频繁的求s(m)时，第一种方法不适用，当我们频繁的修改数组a时，第二种方法每次都要修改数组s，修改数组s的时间复杂度为O(n)

而树状数组可以很好解决这种场景，它类似方法二
方法二中我们定义s[m] = a[m]+a[m-1]+a[m-2]+....+a[0]
树状数组中我们定义s[m]= a[m-1]+a[m-2]+....+a[i-2^k],其中k为m的二进制的第一个1前0的个数
ps:有些资料是m至i-2^k+1,那是数组下标从1开始计数的，这里下标从0开始，因此有所区别

举个例子：10的二进制1010，因此k=1；24的二进制11000，因此k=3
我们记lowbit(m)=2^k,即有lowbit(10)=2,lowbit(24)=8
可以发现2的二进制是10,8的二进制是1000，因此lowbit的实现很简单

 static int lowbit (int x){
        return x&(-x);
    }

如果这方法无法理解，建议看下二进制补码

接下来数组s就有的一个公式
s[m]=a[m-1]+a[s-2]+....+a[i-lowbit(m)]

我觉得树状数组讲到这里就可以了，为了便于理解，我举一个例子，测试代码如下

    public static void main(String[] args) {
        for (int i = 0; i < 30; i++) {
            System.out.println("i = " + intFixedString(i) + " binary i = " + intBinaryString(i) + " lowbit = " + lowbit(i) + " i-2^k = " + (i - lowbit(i)));
        }
    }

    public static String intBinaryString(int i) {
        return Integer.toBinaryString((i & 0xFF) + 0x100).substring(1);
    }

    public static String intFixedString(int i) {
        return i < 10 ? i + " " : i + "";
    }

打印结果

假设求sum(28)，我们分析一下 i = 28 binary i = 00011100 lowbit = 4 i-2^k = 24
s[28]=a[27]+a[26]+....+a[24]
其中最后一个数是24，继续分析 i = 24 binary i = 00011000 lowbit = 8 i-2^k = 16
s[24]=a[23]+a[22]+....+a[16]
最后一个数是16，继续分析 i = 16 binary i = 00010000 lowbit = 16 i-2^k = 0
s[16]=a[15]+a[14]+....+a[0]

很容易发现sum(28)=a[28]+s[28]+s[24]+s[16]，代码实现如下

    public int sum(int m) {
        int sum = a[m];
        while (m >= 0) {
            sum += s[m];
            m = m - lowbit(m);
        } 

        return sum;
    }

上面只是我的个人理解，如有错误，敬请指正。

参考：http://www.cppblog.com/menjit...

云服务器 GPU云服务器二维树状数组树状表树状图树状

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68550.html

运用树状数组解决动态数组求和

摘要：对于一组一维数组解决前项和，如果使用的方法需要的时间来找到前项数字的和，但是可以用的时间来更新对应数字的值但是仍然需要的时间来更新牵扯到相应数字数组的和，相反可以使用树状数组来降低运行时间求数组内一段数组的和，但同样我们增加了更新树状数组内对于一组一维数组解决前n项和，如果使用linear scan的方法, 需要O(n)的时间来找到前n项数字的和，但是可以用O(1)的时间来更新对应数...

Barrior 2019-08-15 13:50 评论0 收藏0
用100行代码画出DOM树状结构

摘要：用行代码画出树状结构这两天写了这样一个小玩具，是一个可以把的树状结构解析，并且画出来的东西，把代码写到左边，右边就会自动生成啦。绘图部分依赖了百度开源的，核心功能的实现只有行代码。如果是或者标签，那么进入相应的状态用100行代码画出DOM树状结构这两天写了这样一个小玩具，是一个可以把DOM的树状结构解析，并且画出来的东西，把HTML代码写到左边，右边就会自动生成啦。点这里看DEM...

Galence 2019-08-21 10:45 评论0 收藏0
localStorage实现本地储存树形菜单

摘要：因为任务需要添加到树的结构上，所以要记录任务是添加到哪个结点上的，需要为每个树结点添加一个作为标识以便于在结点上添加任务，树状结构中每个结点的按照树的先序遍历将结点的依次储存于数组中。 localStorage实现本地储存树形菜单最近在写一个Todo-list的页面，页面布局和操作都写完后，想要用localStorage实现本地储存。然而对储存数据的方法一无所知，就先去了解了web的...

William_Sang 2019-08-21 10:56 评论0 收藏0
关于树形插件展示中数据结构转换的算法

摘要：举例说明如下二维数据结构总部二级门店三级门店二级门店树状数据结构总部二级门店三级门店二级门店但在某些插件中，或在某些特殊场景中，我们有两种数据结构之间相互转换的需求，需要自己写一个辅助函数来完成。问题背景在一些目录结构、机构层级等展示的场景中，我们经常会用到一些成熟的树形插件来进行轻松展示，比如ztree等。大多数插件会支持对两种数据源格式的解析，一种是通用的二维数据结构，一种是树...

王晗 2019-08-21 18:29 评论0 收藏0