深入理解树状数组 | 京东物流技术团队
树状数组
树状数组(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; } }
巨人的肩膀
作者:京东物流 王奕龙
来源:京东云开发者社区 自猿其说Tech 转载请注明来源
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
开源框架 NanUI 作者转行卖钢材,项目暂停开发
NanUI 作者在国庆节发布了停更公告,称该项目将暂停开发,原因是去年被裁员失业后,他已转行销售钢材,现在很难腾出时间来开发和维护 NanUI 项目。 他说道: 为了生存,本人只能花费更多的时间和精力去谈单,去销售,去收款,因此已经很难再腾出时间来开发和维护 NanUI 项目,对此我深感无奈,也希望后面生活和工作稳定后能腾出时间来继续维护 NanUI。 NanUI 作者表示,他所在公司因疫情于去年(2022 年)初彻底宣布裁减所有开发岗位,因此他也只能顺应大流在 36 岁这个尴尬的年纪失业。 viahttps://github.com/XuanchenLin/NanUI/discussions/367 NanUI 界面组件是一个开放源代码的 .NET / .NET Core 窗体应用程序(WinForms)界面框架。它适用于希望使用 HTML5/CSS3 等前端技术来构建 Windows 窗体应用程序用户界面的 .NET 开发人员。 NanUI 基于谷歌可嵌入的浏览器框架 Chromium Embedded Framework (CEF),因此用户可以使用各种前端技术 HTML5/CS...
- 下一篇
IDEA工具第一篇:细节使用-习惯设置 | 京东云技术团队
安装好Idea后,直接上手clone代码进入编码时代,有没有那么一刻你会觉用起来没有那么顺手流畅呢? 👉👉👉 下面是关于 【Windows】 下安装idea的一些习惯设置👈👈👈【 Mac大致一样 】 一、修改系统文件 • 默认:Idea默认系统配置和插件安装在C盘下,启动前先进行修改,防止占用C盘资源(毕竟windows C盘资源有限,想必大家最多分配100G或者200G内存吧😭) • 具体操作:Idea安装目录下的bin目录,修改idea.properties文件 二、设置Idea启动时先选择项目再进入 • Settings --> Appearance & Behavior --> System Settings【或者直接 Settings --> 搜素system settings】取消勾选Reopen last project on startup 三、设置编码 • 编码这个就不用说了吧,每次调整配置文件提交,别人打开总是乱码,当整个团队设置了编码,哪里还会出现这个问题😬 • 具体操作:Settings --> E...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Linux系统CentOS6、CentOS7手动修改IP地址
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- CentOS7设置SWAP分区,小内存服务器的救世主
- CentOS7安装Docker,走上虚拟化容器引擎之路
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- Red5直播服务器,属于Java语言的直播服务器
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库