区块链技术博客
www.b2bchain.cn

算法-树状数组

这篇文章主要介绍了算法-树状数组,通过具体代码讲解6048并且分析了算法-树状数组的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了算法-树状数组。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=6048。具体如下:

算法 树状数组

算法

发布日期:   2019-12-12
文章字数:   1.1k
阅读时长:   4 分
阅读次数:  

树状数组

一、树状数组概念

Binary Indexed Tree,用于维护前缀信息的结构,对前缀信息处理也十分高校,用于解决前缀信息问题和区间类问题。

比如:给定一个数组,实现两个函数

  • update(int index,int val),将数组下标为index的元素改为val
  • querySum(int start,int end),返回区间内元素和

这两个用线段树求过很多遍了。树状数组也是通过前缀和的思想来完成单点更新和区间查询。它比线段树用的空间更小,速度更快。

二、树状数组算法分析

注意:树状数组的下标从 1 开始计数。定义数组 C 是一个对原始数组 A 的预处理数组。

由原数组构造树状数组

算法-树状数组

算法-树状数组

算法-树状数组

算法-树状数组

算法-树状数组

结论:C[i]来自几个数组A中的元素:取决于i的二进制末尾有几个连续的0。比 如有k个0,那么C[i]来自2^k^个A中的元素。

算法-树状数组

如果i是当前位置,当前有 $2^k$ 个来自A中的元素,有哪 $2^k$ 个呢?就是从C[i]的正下方出发,往前数 $2^k$ 个,C[i]就是这2^k^个数的和。

定义一个 $lowbit(i) = 2^k$ 函数,就是把下标i传到函数中来,返回 $2^k$,lowbit表示C[i]这个数值是由A中的多少个元素相加得来的。(根据上面一段,你还能找到这几个元素是啥,从C[i]的正下方开始往前数2^k^个)

怎么找父亲节点?i+lowbit(i) = 父亲比如C[4],4的lowbit是4,它有个宽度为4的梯子,这个梯子就是它到它父亲的距离宽度。4+lowbit(4) = 8。再比如6,6的lowbit是2,6+2 = 8

算法-树状数组

三、lowbit函数

lowbit函数用到了补码相关知识。给定一个数,比如12,我们能求得它的二进制1100,如何求-12的二进制?实际上二进制前面有个符号位,正数前面符号位是0,负数前面符号位是1,12的二进制实际上是01100,那么求-12的二进制有两步

  • 首先把符号位从0改成1,然后对12每位取反。变成10011
  • 最后+1,即10011+1 = 10100,这就是-12的二进制

推荐一篇关于原码、反码、补码博客

lowbit(i) = 2^k,它就是利用了正数和负数的二进制

num & (-num) = 2^k

四、树状数组的构建、修改、查询

1、构建

把原始数组A和预处理数组C都初始化为0,每更新一个元素,都要把它的值累加到它父亲的值上面去。比如初始化A1后,要把它的值累加到它父亲C1上面去,C1接收到值后,还要把C1的值传递给C2,然后C2传递给C4,C4传递给C8,如果A1的值为10,那第一次更新完就是这个样子

算法-树状数组

再更新A2,C2就要开始累加A2的值,并传给C2的父亲们,比如A2为5,就是下面这样子

算法-树状数组

2、更新

比如我要把A1从10改为1,那么就会有一个差值delta为9,C1更新成1,然后不断传给它的父亲们继续更新。

3、查询

想要查询区间[i,j]的和,首先要查询区间[1,j](树状数组起点从1开始的)和区间[1,i-1]的和,前者减去后者就是我们要求的答案。

这里还有个求前缀和[1,i]的公式,是推导出来的,sum(i) = sum(i - lowbit(i)) + C[i]

class BinaryIndexedTree{         private int[] A, C; //定义原始数组A和预处理数组C          //init         public BinaryIndexedTree(int[] nums) {             int n = nums.length;             A = new int[n];             C = new int[n + 1];              for (int i = 0; i < n; i++) {                 update(i, nums[i]);             }         }          public void update(int index, int val) {             int delta = val - A[index]; //得到新val与原val的差值             A[index] = val;             /**              * 从index+1开始,因为C数组我们定义从1开始的。              * 每次更新完C[index+1],还要再继续更新它的父亲。距离就是宽度lowbit(i)              */             for (int i = index + 1; i <= A.length; i += lowbit(i)) {                 C[i] += delta;             }         }          public int querySum(int start, int end) {             return getPrefixSum(end) - getPrefixSum(start - 1);         }          //获取前缀和         public int getPrefixSum(int index) {             int sum = 0;             /**              * 从正下方开始,先找到它前面2^k个的和,比如6,就是找到它前两个(包括它自身)              * i = i - lowbit(i)意思是,找完那2^k个,下一个应该从C[4]开始找了              */             for (int i = index + 1; i > 0; i -= lowbit(i)) {                 sum += C[i];             }             return sum;         }          private int lowbit(int index) {             return index & (-index);         }     }


算法 树状数组

线程池源码整体架构 首先来了一个任务,先判断下核心线程池里的线程数有没有达到设定的值,如果没有,就可以新建个Worker出来处理任务,处理任务的时候如果这个任务为空,那这个worker就阻塞住,因为这个任务不需要处理,如果这个任务不为空,
2020-03-01 Java集合源码
线段树概念:线段树就是一棵二叉树,每个节点代表一个区间,主要用于解决区间类问题。每个节点的属性根据需要可以去自定义,比如节点的属性可以是区间和、区间最大/最小值。。 一、线段树节点定义每个node有区间的左右端点,以及左右孩子 publi
2019-12-12 算法

本文地址https://www.b2bchain.cn/?p=6048

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 算法-树状数组
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们