C++实用数据结构:二叉索引树

时间:2022-09-17 15:29:54

看下面这个问题(动态连续和查询):

有一个数组A(长度为n),要求进行两种操作:
add(i,x):让Ai增大x;
query(a,b):询问Aa+Aa+1+...+Ab的和;
若进行模拟,则每次query操作的最坏的时间复杂度为O(n),在n较大时速度较慢。用前缀和也不能提高效率(每次add操作最坏为O(n))。有一种数据结构,可以在O(n)时间里初始化,用O(logn)的速度执行add操作或查询前缀和,从而执行query操作。
首先,我们来介绍“lowbit”。对于一个数x,lowbit(x)是x的二进制里最右面的1所代表的数字,例如lowbit(20)=4,因为20的二进制为10100,最右面的1代表4。怎样计算lowbit呢?很简单,lowbit(x)=x&-x。这是因为负数是用补码保存的,-x就相当于(~x)+1。例(用8位计算):
 20=(00010100)
-20=(11101100)
现在我们来介绍二叉索引树。二叉索引树在程序中也是用数组来保存的。
C++实用数据结构:二叉索引树(画得难看请见谅)
图中,深灰色方块代表树中的结点(结点0为虚拟结点),灰色线段代表树中的边。这些边并不需要显式保存;对于一个节点x,若它是父结点的左子结点,则父结点编号为x-lowbit(x),否则为x+lowbit(x)。图中的每个结点左侧都有一个白色长条(包括它自己),如结点4的长条为1~4,节点3的长条为3~3。不难发现,结点x的长条为(x-lowbit(x)+1)~x。
然后,我们用一个数组S储存每个结点的白色长条内的所有数的和。例如,S4=A1+A2+A3+A4。这样,就可以使用一个辅助的前缀和数组,在O(n)时间内从左到右初始化S数组。代码如下:
 
 
 int n;
 int S[maxn],A[mxan],S1[maxn];
 int begin()
 {
     memset(S1,,sizeof(S1));
     ;i<=n;i++)
     {
         S1[i]=S1[i-]+A[i];
         S[i]=S1[i]-S1[i-lowbit(i)];
     }
 }
最后让我们来实现add操作和查询操作。对于某个add操作的结点i,它的修改会影响到那些结点呢?很显然,在它下面的结点(lowbit比它小)不会受到影响,在它左边的结点也不会受到影响,所以只需要考虑在它右边且lowbit比它大的第一个结点,这个结点的白色长条一定覆盖x。很显然,这个结点的编号为i+lowbit(i)。
接下来,x结点不需要考虑了,让我们来考虑i+lowbit(i)结点。与上面一样,只需要考虑在它右边且lowbit比它大的第一个结点,所以只需要让i+=lowbit(i)。代码如下:
 void add(int i,int x)
 {
     //若需要其他操作,可以加一句:
     //A[i]+=x;
     while(i<=n)
     {
         S[i]+=x;i+=lowbit(i);
     }
 }

查询前缀和的方法与之类似,只是i+=lowbit(i);改成了i-=lowbit(i);这里不再介绍证明方法,与上面类似。代码如下:

 int query2(int i)
 {
     ;
     )
     {
         sum+=S[i];i-=lowbit(i);
     }
     return sum;
 }
 int query(int l,int r)
 {
     );
 }
最后,若有建议请提出。

C++实用数据结构:二叉索引树的更多相关文章

  1. 【转载】区间信息的维护与查询(一)——二叉索引树(Fenwick树、树状数组)

    在网上找到一篇非常不错的树状数组的博客,拿来转载,原文地址. 树状数组 最新看了一下区间的查询与修改的知识,最主要看到的是树状数组(BIT),以前感觉好高大上的东西,其实也不过就这么简单而已. 我们有 ...

  2. 二叉索引树BIT

    定义     二叉索引树,binary index tree,又名树状数组,或Fenwick Tree,因为本算法由Fenwick创造.     对于数组A,定义Query(i,j) = Ai +Ai ...

  3. POJ 3321 Apple Tree dfs&plus;二叉索引树

    题目:http://poj.org/problem?id=3321 动态更新某个元素,并且求和,显然是二叉索引树,但是节点的标号不连续,二叉索引树必须是连续的,所以需要转化成连续的,多叉树的形状已经建 ...

  4. NYOJ 116 士兵杀敌(二)(二叉索引树)

    http://acm.nyist.net/JudgeOnline/problem.php?pid=116 题意: 南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的. 小工是南将军手下的 ...

  5. HDU 1166 敌兵布阵(线段树 or 二叉索引树)

    http://acm.hdu.edu.cn/showproblem.php?pid=1166 题意:第一行一个整数T,表示有T组数据. 每组数据第一行一个正整数N(N<=50000),表示敌人有 ...

  6. 【树状数组(二叉索引树)】轻院热身—candy、NYOJ-116士兵杀敌(二)

    [概念] 转载连接:树状数组 讲的挺好. 这两题非常的相似,查询区间的累加和.更新结点.Add(x,d) 与 Query(L,R) 的操作 [题目链接:candy] 唉,也是现在才发现这题用了这个知识 ...

  7. 二叉索引树,LA2191,LA5902,LA4329

    利用了二进制,二分的思想的一个很巧妙的数据结构,一个lowbit(x):二进制表示下的最右边的一个1开始对应的数值. 那么如果一个节点的为x左孩子,父亲节点就是 x + lowbit(x),如果是右孩 ...

  8. 树状数组(二叉索引树 BIT Fenwick树) &ast;【一维基础模板】(查询区间和&plus;修改更新)

    刘汝佳:<训练指南>Page(194) #include <stdio.h> #include <string.h> #include <stdlib.h&g ...

  9. 1&period;红黑树和自平衡二叉&lpar;查找&rpar;树区别 2&period;红黑树与B树的区别

    1.红黑树和自平衡二叉(查找)树区别 1.红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单. 2.平衡 ...

随机推荐

  1. SQL Server 索引

    SQL Server 中数据存储的基本单位是页(Page).数据库中的数据文件(.mdf 或 .ndf)分配的磁盘空间可以从逻辑上划分成页(从 0 到 n 连续编号).磁盘 I/O 操作在页级执行.也 ...

  2. 一个App完成入门篇(四)- 完成反馈页面

    上一节中我们学会了如何通过点击不同按钮切换页面,这节专注于完成反馈页面的功能以及细节动画. 导入项目 添加新组件 同步新组件 完成页面布局 输入时加动画效果 弹出日期选择 直接引用UI页面 将要学习的 ...

  3. 基础2 JVM

    1. 内存模型以及分区,需要详细到每个区放什么. //运行时数据区域 方法区 Method Area 各个线程共享的内存区域 存储已被虚拟机加载的类信息 常量 静态变量 即时编译器编译后的代码 虚拟机 ...

  4. java 多线程7(线程的停止)

    notify(): 是很温和的唤醒线程的方法,它不可以指定清除哪一个异常 interrupt(): 粗暴的方式,强制清除线程的等待状态,被清除的线程会接收到一个InterruptedException ...

  5. mapreduce程序来实现分类

    文件的内容例如以下所看到的: 5 45 8 876 6 45 要求最后的输出格式: 1    5 2    6 3    8 4    45 5    45 5    876 首先,这个题目是须要对文 ...

  6. 2016年团体程序设计天梯赛-决赛 L1-2&period; I Love GPLT(5)

    这道超级简单的题目没有任何输入. 你只需要把这句很重要的话 —— “I Love GPLT”——竖着输出就可以了. 所谓“竖着输出”,是指每个字符占一行(包括空格),即每行只能有1个字符和回车. #i ...

  7. 小程序组件化框架 WePY 在性能调优上做出的探究

    作者:龚澄 导语 性能调优是一个亘古不变的话题,无论是在传统H5上还是小程序中.因为实现机制不同,可能导致传统H5中的某些优化方式在小程序上并不适用.因此必须另开辟蹊径找出适合小程序的调估方式. 本文 ...

  8. 暑期OI大电影——不看后悔整个OI生涯!

    惊爆~!! 2018暑期OI大电影要开始放送啦~!! 各位OI骨灰级大咖登场荧幕~!! 近四十部大电影纷至沓来~!! 著名特级导演CCF.著名特级编剧刘汝佳等纷纷给予高度评价~!! 观众朋友们,OI的 ...

  9. nyoj 吃土豆

    吃土豆 时间限制:1000 ms  |  内存限制:65535 KB 难度:4   描述 Bean-eating is an interesting game, everyone owns an M* ...

  10. cocos2dx2&period;x 创建项目

    cocos2d-x下载地址:http://www.cocos2d-x.org/download 2.0之后的创建项目比较easy了 第一步,首先 cd cocos2d-x-2.2.1/tools/pr ...