- 浏览: 603993 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
一、树状数组是干什么的?
平常我们会遇到一些对数组进行维护查询的操作,比较常见的如,修改某点的值、
求某个区间的和,而这两种恰恰是树状数组的强项!当然,数据规模不大的时候,对于修改某点的值是非常容易的,复杂度是O(1),但是对于求一个区间的和就要扫一遍了,复杂度是O(N),如果实时的对数组进行M次修改或求和,最坏的情况下复杂度是O(M*N),当规模增大后这是划不来的!而树状数组干同样的事复杂度却是O(M*lgN),别小看这个lg,很大的数一lg就很小了。
二、树状数组的定义
如图所示,红色矩形表示的数组C[]就是树状数组。
给定序列(数列)A,我们设一个数组C满足
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
……
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
......
定义:
C[t] = A[t – 2^k + 1] + … + A[t],k为t在二进制下末尾0的个数。(t>=1)
分析上面的几组式子可知,当 t 为奇数时,Ct=Ai ;当 t为偶数时,就要看 t的因子中最多有二的多少次幂,例如,6 的因子中有 2 的一次幂,等于 2 ,所以 C6=A5+A6(由六向前数两个数的和),4 的因子中有 2 的两次幂,等于 4 ,所以 C4=A1+A2+A3+A4(由四向前数四个数的和)。
三、基本操作
(1)C[t]展开以后有多少项?由下面公式计算:
(2)修改
当我们修改A[i]的值时,可以从C[i]往根节点一路上溯,调整这条路上的所有C[]即可,对于节点i,父节点下标 p=i+lowbit(i)
平常我们会遇到一些对数组进行维护查询的操作,比较常见的如,修改某点的值、
求某个区间的和,而这两种恰恰是树状数组的强项!当然,数据规模不大的时候,对于修改某点的值是非常容易的,复杂度是O(1),但是对于求一个区间的和就要扫一遍了,复杂度是O(N),如果实时的对数组进行M次修改或求和,最坏的情况下复杂度是O(M*N),当规模增大后这是划不来的!而树状数组干同样的事复杂度却是O(M*lgN),别小看这个lg,很大的数一lg就很小了。
二、树状数组的定义
如图所示,红色矩形表示的数组C[]就是树状数组。
给定序列(数列)A,我们设一个数组C满足
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
……
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
......
定义:
C[t] = A[t – 2^k + 1] + … + A[t],k为t在二进制下末尾0的个数。(t>=1)
分析上面的几组式子可知,当 t 为奇数时,Ct=Ai ;当 t为偶数时,就要看 t的因子中最多有二的多少次幂,例如,6 的因子中有 2 的一次幂,等于 2 ,所以 C6=A5+A6(由六向前数两个数的和),4 的因子中有 2 的两次幂,等于 4 ,所以 C4=A1+A2+A3+A4(由四向前数四个数的和)。
三、基本操作
(1)C[t]展开以后有多少项?由下面公式计算:
int lowbit(int t){//计算c[t]展开的项数 return t&(-t); } 例: lowbit(1)=1 C1 = A1 lowbit(2)=2 C2 = A1 + A2 lowbit(3)=1 C3 = A3 lowbit(4)=4 C4 = A1 + A2 + A3 + A4 lowbit(5)=1 C5 = A5 lowbit(6)=2 C6 = A5 + A6 lowbit(7)=1 C7 = A7 lowbit(8)=8 C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 ....... c[t]展开的项数就是lowbit(t),c[t]就是从a[t]开始往左连续求lowbit(t)个数的和, lowbit(1)=1 lowbit(2)=2 lowbit(3)=1 lowbit(4)=4 lowbit(5)=1 lowbit(6)=2 lowbit(7)=1 lowbit(8)=8 lowbit(9)=1 lowbit(10)=2 lowbit(11)=1 lowbit(12)=4 lowbit(13)=1 lowbit(14)=2 lowbit(15)=1 lowbit(16)=16 lowbit(17)=1 lowbit(18)=2 lowbit(19)=1 lowbit(20)=4 lowbit(21)=1 lowbit(22)=2 lowbit(23)=1 lowbit(24)=8 lowbit(25)=1 lowbit(26)=2 lowbit(27)=1 lowbit(28)=4 lowbit(29)=1 lowbit(30)=2 lowbit(31)=1 lowbit(32)=32 lowbit(33)=1 lowbit(34)=2 lowbit(35)=1 lowbit(36)=4 lowbit(37)=1 lowbit(38)=2 lowbit(39)=1 lowbit(40)=8 lowbit(41)=1 lowbit(42)=2 lowbit(43)=1 lowbit(44)=4 lowbit(45)=1 lowbit(46)=2 lowbit(47)=1 lowbit(48)=16 lowbit(49)=1 lowbit(50)=2 lowbit(51)=1 lowbit(52)=4 lowbit(53)=1 lowbit(54)=2 lowbit(55)=1 lowbit(56)=8 lowbit(57)=1 lowbit(58)=2 lowbit(59)=1 lowbit(60)=4 lowbit(61)=1 lowbit(62)=2 lowbit(63)=1 lowbit(64)=64
(2)修改
当我们修改A[i]的值时,可以从C[i]往根节点一路上溯,调整这条路上的所有C[]即可,对于节点i,父节点下标 p=i+lowbit(i)
代码实现: //增加某个元素的大小,给某个节点 i 加上 x update(int i,int x){ while(i<=n){ c[i]=c[i]+x; i=i+lowbit(i); } } (3)求数列的前n项和,只需找到n以前的所有最大子树,把其根节点的C加起来即可。 int Sum(int n) //求前n项的和. { int sum=0; while(n>0) { sum+=c[n]; n=n-lowbit(n); } return sum; } 例: public class TreeArray{ int n;//数组元素个数 int[] a;//原数组 int[] c;//对应的树状数组 public TreeArray(int[] a){ n=a.length; this.a=a; c=new int[a.length]; for(int i=1;i<a.length;i++){ for(int j=0;j<lowbit(i);j++) c[i]=c[i]+a[i-j]; } } private int lowbit(int t){//计算c[t]展开的项数 return t&(-t); } private void update(int i,int x){ while(i<=n){ c[i]=c[i]+x; i=i+lowbit(i); } } private int Sum(int k){ //求前k项的和. int sum=0; while(k>0){ sum+=c[k]; k=k-lowbit(k); } return sum; } public static void main(String args[]){ int a[]={0,1,2,3,4,5,6,7,8,9,10}; TreeArray ta=new TreeArray(a); System.out.println(ta.Sum(10)); ta.update(5,-20); System.out.println(ta.Sum(10)); System.out.println(ta.Sum(4)); } } 运行: C:\java>java TreeArray 55 35 10
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2404北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1988import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1912POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1400接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2470当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1843关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1844关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1822关于树状数组,请参考:http://128kj.iteye.c ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2121POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2595设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2136继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2559继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2727先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2306一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2064形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2855例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2147字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18732堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4069一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3335前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
循环队列的头指针和尾指针重合时如何判断队空还是队满...对树的先做初步了解,先对二叉树进行详细研究再回来。 二叉树不是树: 虽然定义与有序树比较像 当只有一个子结点的时候,有序树只有一种,但是二叉树有两种(子
另外,我们可能还需要用链表或树形结构来保存历史棋局记录,以便进行回溯操作。 2. **函数定义**: - `place_stone`: 这个函数接受棋盘状态和一个位置(行和列)作为参数,放置一颗棋子并更新棋盘状态。 - `check...
在【描述】中,提到了本课程将涉及的主要内容,包括数据结构的基本概念、线性表、栈、队列、字符串、数组、树形结构、图结构、查找和排序等。这些是数据结构的基本组成部分,通过学习这些内容,可以理解和运用不同的...
它的核心思想是维护一个树状结构,每个节点代表一个集合,节点的父节点表示其所在的集合。在并查集中,通常有两种操作:查找(Find)和连接(Union)。 查找操作(Find)用于确定一个元素属于哪个集合,通常采用...
此外,会讨论几种基本的数据结构类型,如线性结构、树形结构、图状结构和集合,并对C语言中的基本数据类型和数据结构做简要介绍。 第二章:线性表 线性表是最基础的数据结构之一,包括顺序表和链表。在C语言中,...
数组、广义表、树和图等数据结构都是非线性结构。 (2)线性表的顺序存储结构具有以下两个基本特点: ① 线性表中所有元素所占的存储空间是连续的; ② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ...
4. **Chap4.ppt** - 第四章可能涉及到树形结构,如二叉树的定义、性质、遍历方式(前序、中序、后序),以及特殊类型的树,如满二叉树和完全二叉树。 5. **Chap5.ppt** - 第五章可能进一步讨论二叉树,如平衡二叉树...
这包括二进制系统、数据类型(如整型、浮点型、字符串等)、文件类型(文本、图像、音频、视频)及其编码,以及数据的存储结构(如顺序、链式、树形、图结构)。 5. **编程入门**:为了让学生初步理解编程思想,...
- **递归算法**:掌握递归算法,解决树形结构、组合数学等问题,通过调用自身来解决问题。 #### 第八章:集合和记录类型 - **集合类型**:定义和使用集合,用于存储无序且不重复的元素集合。 - **记录类型**:...
主要涉及线性结构(如数组、链表)、树形结构(如二叉树、堆)、图结构、排序算法(如快速排序、归并排序)和查找算法(如二分查找、哈希查找)等。在实际编程中,选择合适的数据结构能显著提升程序的性能和可维护性...
第3次作业可能深入到树形结构,如二叉树。二叉树每个节点最多有两个子节点,分为左子节点和右子节点。二叉树有多种类型,如完全二叉树和平衡二叉树,如AVL树和红黑树,它们在搜索、排序等领域有广泛应用。学习二叉树...
在树形结构的教学中,学生会接触到树、二叉树的概念、性质和存储结构。二叉树的遍历算法是课程中的一个难点,包括前序遍历、中序遍历和后序遍历等。哈夫曼树和编码部分讲述了如何通过构造最优二叉树来实现数据的压缩...
6. **网络分类**:按拓扑结构和地域划分的网络类型,如总线型、星型、环形、树形,以及局域网、城域网、广域网和网间网。 7. **域名表示**:理解URL格式,如http://www.yizhong.xm.fj.cn。 **第三部分:数据结构** ...
这些算法是处理图和树形结构数据时不可或缺的工具。通过动态演示,学习者能够看到访问节点的顺序和路径选择,加深对算法细节的理解。此外,系统还可能展示了数据结构的其他操作,如树的平衡调整,图的连通性检测等。...
从简单的数组、链表到复杂的树形结构、图,再到特定场景下的散列表、堆等,不同的数据结构适用于不同的应用场景。掌握数据结构的基本知识,对于解决实际问题、提升算法能力有着重要作用。 网络原理是计算机科学中不...
树形结构在实际应用中非常广泛,例如用于构建数据库索引、文件系统等。 - **二叉树**:每个节点最多有两个子节点的树。 - **二叉查找树**:每个节点的左子树中的所有节点的值均小于该节点的值,右子树中的所有节点...
在文档中虽然未给出完整解释,但从“AVL”字样可以推测考题涉及数据结构中的树形结构及其平衡操作。 12. 操作系统:文档提到了DBTG CODASYL,这是关于数据库系统管理的组织,同时也是数据库管理系统的一个标准。它...
3. **搜索算法**:如二分查找、广度优先搜索(BFS)和深度优先搜索(DFS),这些都是在数据结构中寻找元素或遍历树形结构的关键技术。 4. **图算法**:包括Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法...
它提供了一种层次化的数据组织方式,使得数据可以被结构化为树形结构,便于管理和访问。然而,随着大数据时代的到来,HDF4逐渐无法满足需求,于是HDF5应运而生。HDF5在HDF4的基础上进行了扩展和优化,支持更大的文件...