深入理解树状数组

这篇具有很好参考价值的文章主要介绍了深入理解树状数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

树状数组

树状数组(BIT, Binary Indexed Tree)是简洁优美的数据结构,它能在很少的代码量下支持单点修改区间查询,我们先以a[] {1, 2, 3, 4, 5, 6}数组为例建立树状数组看一下树状数组的样子:

可以发现:不是所有节点都是连接在一起的,c[1], c[2], c[3], c[4] 和 c[5], c[6] 分别构成了两棵树;奇数索引位置的节点只管辖一个数组元素(我们例子中以 1 为起始索引)。那么这个树状数组是怎么计算和推导出来的呢?

管辖的区间

树状数组的每个元素会管辖多少个数组元素?也就是说每个元素的区间长度是多少?我们从上图中已经知道了奇数的树状数组元素只管辖一个元素,区间为 c[x] = [x, x],那么我们只需再研究下偶数元素管辖的区间长度即可。

  • c[y] 所管辖的区间长度为 2k,其中 k 为 y 的 2 进制表示中最低位 1 后面所有 0 的数量;c[y] 所管辖的区间为:[y - 2k+ 1, y]

我们以 c[4] 为例,它管辖多少个元素呢?4 的 2 进制表示为 0100,最低位 1 后面 0 的数量为 2,即 k = 2,那么 2k= 22= 4,所以它管辖的区间长度为 4,也就是 4 个数组元素,区间为 [4 - 4 + 1, 4] = [1, 4]。

父节点是谁?

现在我们知道每个元素所管辖的区间范围了,那么我们怎么才能知道它的父节点是谁呢?就比如说我们现在得到了 c[1] 元素,我们想知道它的父节点,要怎么计算呢?

  • c[x] 的父节点为 c[x + lowbit(x)]

怎么回事?其中的**lowbit(x)**是什么东西?其实它的值和 2k一致,其中 k 为 x 的 2 进制表示中最低位 1 后面所有 0 的数量,熟悉不熟悉?这个 lowbit(x) 和我们上文中计算该元素所管辖区间长度的值一致!这不就简单了!

  • lowbit(x) 的计算方法:lowbit(x) = x & -x

    我们以计算 c[2] 为例,lowbit(2) = 2 & -2,其中 2 的 2 进制表示为 0010,-2 的 2 进行表示为 1110,它的计算方法为将 2 的所有非符号位二进制全部取反后再加 1,即 1101 + 1 = 1110,执行 & 运算后结果为 0010,十进制表示为 2,与 21值一致。lowbit 的计算用代码表示为:

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

我们以 c[1] 节点为例计算下它的父节点是谁,lowbit(1) = 1 & -1 = 0001 & 1111 = 0001 = 1,那么它的父节点为 c[1 + 1] = c[2],与图上表示的一致。


现在我们已经知道如何通过计算来创建树状数组了, 接下来我们要看下它的应用。

区间查询

区间查询我们先讨论计算前 N 项和的方法,比如我们现在要查询前 6 项和,我们来看下它查询的过程:

  • 从 c[6] 开始找子节点,有 c[6] 管辖的区间为 [5, 6],那么再往下找需要找 c[4],它的区间为 [1, 4],计算这两个节点的和即可。

那么从 c[6] 跳到 c[4] 是如何计算出来的呢?我们可以通过 c[6] 区间的下界减 1 来得到,转换成公式表示即为 x - lowbit(x) = 6 - 2 = 4,当它跳到 c[4] 时发现已经满足求和条件,不再向下跳而结束查找,而且我们可以通过计算 4 - lowbit(4) = 4 - 4 = 0 ,可以发现当 x - lowbit(x) = 0 时为结束查找的条件。我们用代码来表示为:

    int query(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            res += c[i];
        }
        
        return res;
    }


那么我们计算区间 [3, 6] 的和该如何计算呢?我们从图中可以发现,先计算出[1, 6] 和 [1, 2] 的和,再使用前者减去后者即为所得,用代码表示为:

    int query(int left, int right) {
        return query(right) - query(left - 1);
    }


单点修改

如果我们要修改 a[x] 的值,我们仅需要修改所有管辖了 a[x] 的 c[y] 即可,而 a[x] 可能会被多个 c[y] 管辖,这些所有的 c[y] 节点该如何确定呢?我们可以回头再去看看前面的树状数组配图,比如我们要修改 a[1] 的值,那么我们需要修改 c[1], c[2] 和 c[4] ,能不能发现它是在不断的跳父节点修改?所以,如果我们要修改数组中某个元素的值,树状数组的更新则是不断地更新父节点值。好,我们直接上代码吧:

    // 将 index 索引处的值更新为 num
    void update(int index, int num) {
        a[index] = num;
        add(index, num - a[index]);
    }

    // 更新 c[index] 的值,变化差值为 val
    void add(int index, int val) {
        for (int i = index; i <= c.length; i += lowbit(i)) {
            c[i] += val;
        }
    }


建树

好了,区间查询和单点修改我们都讲完了,但是从头到尾我们还没说过树状数组是怎么建立的呢。我们可以想一下,c 数组初始化时每个索引处的值都为 0,建树仅需要将 a 数组中所有值都在树状数组中执行单点修改即可:

    public BinaryIndexedTree(int[] a) {
        this.a = a;
        this.c = new int[a.length + 1];
        
        for (int i = 0; i < a.length; i++) {
            add(i + 1, a[i]);
        }
    }


到这里我们基本上已经将树状数组讲解完毕了,它的全量代码如下:

public class BinaryIndexedTree {

    int[] a;

    int[] c;

    public BinaryIndexedTree(int[] a) {
        this.a = a;
        this.c = new int[a.length + 1];

        for (int i = 0; i < a.length; i++) {
            add(i + 1, a[i]);
        }
    }

    // 将 index 索引处的值更新为 num
    void update(int index, int num) {
        a[index] = num;
        add(index, num - a[index]);
    }

    // 更新 c[index] 的值,变化差值为 val
    void add(int index, int val) {
        for (int i = index; i < c.length; i += lowbit(i)) {
            c[i] += val;
        }
    }

    int query(int left, int right) {
        return query(right) - query(left - 1);
    }

    // 查询前缀和的方法
    int query(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            res += c[i];
        }

        return res;
    }

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



巨人的肩膀

  • 树状数组(简单介绍)

  • 负数的二进制表示方法(正数:原码、负数:补码)

  • 树状数组

  • 算法学习笔记(2) : 树状数组

  • 维基百科 - 树状数组

  • 关于各类「区间和」问题如何选择解决方案(含模板)

  • 算法学习笔记(19): 离散化

作者:京东物流 王奕龙

来源:京东云开发者社区 自猿其说Tech 转载请注明来源文章来源地址https://www.toymoban.com/news/detail-711662.html

到了这里,关于深入理解树状数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 树状数组笔记

    数组、前缀和、树状数组的区别:         数组:修改某点O(1),求区间O(n)         前缀和:修改某点O(n),求区间O(1)         树状数组:修改某点O(logn),求区间O(logn) 树状数组采取折中的方式,降低整体的时间复杂度。 由于算法复杂度取决于最坏的情

    2024年02月15日
    浏览(36)
  • 树状数组的扩展应用

    「观前提醒」 「文章仅供学习和参考,如有问题请在评论区提出」 目录 O(N) 建树 方法一 方法二 维护区间和 单点修改,区间查询 区间修改,单点查询 区间修改,区间查询 维护二维子矩阵和(二维树状数组) 单点修改,子矩阵查询 子矩阵修改,单点查询 子矩阵修改,子矩

    2024年02月15日
    浏览(32)
  • 树状数组

    「观前提醒」 「文章仅供学习和参考,如有问题请在评论区提出」 目录 定义 基本概念 基本原理 单点修改 分析 代码实现 区间查询 分析 代码实现 整体代码 练手题目 小结 参考资料 树状数组 是一种支持 单点修改 和 区间查询 的数据结构。 普通的树状数组 只能用来维护像

    2024年02月16日
    浏览(35)
  • 超详细の树状数组讲解!

    以下有错误的话欢迎指正 由于篇幅问题每道题目的代码在每一板块最后折叠给出 其实线段树能维护的东西比树状数组能维护的东西多得多,但是树状数组代码好写啊! 最为常用的树状数组,我们一般都是用这个来解决问题,二维的后面会讲。 我们在进行数列操作的时候,经

    2024年02月07日
    浏览(34)
  • 【算法】树状数组和线段树

    O ( l o g n ) O(logn) O ( l o g n ) :单点修改、区间查询 与前缀和的区别: 前缀和是离线的,每次动态修改原数组某个元素,都需要重新求一遍前缀和,因此单点修改是 O ( n ) O(n) O ( n ) 的,区间查询则是 O ( 1 ) O(1) O ( 1 ) 树状数组是在线的,单点修改和区间查询都是 O ( l o g n ) O(

    2024年02月19日
    浏览(47)
  • 数据结构<1>——树状数组

    前言:树状数组能解决的问题线段树一定可以解决。然后关于线段树的内容会在2中讲解。 树状数组,也叫Fenwick Tree和BIT(Binary Indexed Tree),是一种支持 单点修改 和 区间查询 的,代码量小的数据结构。 那神马是单点修改和区间查询?我们来看一道题。 洛谷P3374(模板): 在本题中

    2024年01月25日
    浏览(61)
  • 树状数组练习题

    为什么大佬们一眼看出是树状数组呢? 不是一眼看出树状数组,而是 要把 【找两个相邻的最小值之间还有几个数没删掉】 的问题转变成动态区间和问题,这个转化过程才是最重要的 , 至于你用什么数据结构求动态区间和是次要的,很多数据结构都能做,最常用的树状数组

    2024年02月03日
    浏览(39)
  • 【C语言】指针的入门篇2,深入理解指针和数组的关系

    欢迎来CILMY23的博客喔,本期系列为【C语言】指针的入门篇2,深入理解指针和数组的关系,图文讲解指针和数组关系的知识,带大家理解指针和数组的关系,以及指针+数组的用法,感谢观看,支持的可以给个赞哇。 前言 在上一篇博客中,我们了解了指针就是地址,并且把地

    2024年02月20日
    浏览(51)
  • 243. 一个简单的整数问题2(树状数组)

    输入样例: 输出样例:  解析:         一般树状数组都是单点修改、区间查询或者单点查询、区间修改。这道题都是区间操作。                    1. 区间修改用数组数组维护差分数组         2. 区间查询,需要log计算两个端点的前缀和。上图右侧,可以得出,计算

    2024年02月14日
    浏览(38)
  • 【80天学习完《深入理解计算机系统》】第十二天3.6数组和结构体

    专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客,如有问题交流,欢迎评论区留言,一定尽快回复!(大家可以去看我的专栏,是所有文章的目录) 文章字体风格: 红色文字表示:重难点★✔ 蓝色文字表示:思路以及想法★✔ 如果大家觉得有帮助的话,感谢大家帮

    2024年02月10日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包