- 浏览: 599795 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
先看网上的介绍:
线段树也叫区间树,顾名思义,线段树是一种基于区间的树,每个节点表示一个“线段”或“区间”。树的根节点表示是“整体”的区间,左右子树分别表示这个区间的左半边和右半边。
基本结构及性质
假设要构造一个表示N个区间大小的线段树,线段树的根节点表示区间[0,N-1],然后将区间分成两半,分别为左右子树表示,这样的线段树的节点只有2N-1个,是O(N)级别的,如图所示表示构造区间[1-5]的线段树。
1)存储:
线段树可以使用链状结构动态构造,这样的优点是节省空间,空间复杂度在2N,但是缺点就是编程复杂度大,执行效率低;
所以线段树一般是使用一维数组以完全二叉树的方式来存储,类似堆,这样的编程复杂度低,执行效率高,但是耗费空间,一般来讲,这样情况下都是申请4N的空间,关于这方面的分析请见参考资料。
2)基本操作:
线段树支持的操作有:构造,插入,查找,更新,删除;这些操作不一定都有,在实现上也不一定都是一个套路,这都取决于实际问题;实际上,通过在线段树节点上记录不同的信息,线段树可以完成很多不同的任务;线段树的高度为logn,这也就使得线段树可以在O(lgn)的时间完成插入、查询、删除等操作。
例: HDU1754
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。这让很多学生很反感。不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ,和两个正整数A,B。
当C为'Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。
当C为'U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。
Output
对于每一次询问操作,在一行里面输出最高成绩。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
下面是AC过的代码:
源码下载:
线段树也叫区间树,顾名思义,线段树是一种基于区间的树,每个节点表示一个“线段”或“区间”。树的根节点表示是“整体”的区间,左右子树分别表示这个区间的左半边和右半边。
基本结构及性质
假设要构造一个表示N个区间大小的线段树,线段树的根节点表示区间[0,N-1],然后将区间分成两半,分别为左右子树表示,这样的线段树的节点只有2N-1个,是O(N)级别的,如图所示表示构造区间[1-5]的线段树。
1)存储:
线段树可以使用链状结构动态构造,这样的优点是节省空间,空间复杂度在2N,但是缺点就是编程复杂度大,执行效率低;
所以线段树一般是使用一维数组以完全二叉树的方式来存储,类似堆,这样的编程复杂度低,执行效率高,但是耗费空间,一般来讲,这样情况下都是申请4N的空间,关于这方面的分析请见参考资料。
2)基本操作:
线段树支持的操作有:构造,插入,查找,更新,删除;这些操作不一定都有,在实现上也不一定都是一个套路,这都取决于实际问题;实际上,通过在线段树节点上记录不同的信息,线段树可以完成很多不同的任务;线段树的高度为logn,这也就使得线段树可以在O(lgn)的时间完成插入、查询、删除等操作。
例: HDU1754
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。这让很多学生很反感。不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ,和两个正整数A,B。
当C为'Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。
当C为'U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。
Output
对于每一次询问操作,在一行里面输出最高成绩。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
下面是AC过的代码:
import java.io.*; import java.util.*; class Tree { //线段树节点, public Tree L, R; public int ValueL, ValueR; public int maxscore; } public class Main { static int score[] = new int[200010]; static class IntervalTree { //线段树,链式实现 public int pos; public Tree nodes[] = new Tree[400010]; public IntervalTree() { for (int j = 0; j < 400010; j++) { nodes[j] = new Tree(); //所有节点先构建 } } public Tree Build(int L, int R) //建树 { Tree rootTree = nodes[pos++]; rootTree.ValueL = L; rootTree.ValueR = R; if (L == R) { rootTree.maxscore = Math.max(score[L], score[R]); return rootTree; } else { int mid; mid = (L+R)/2; rootTree.L = Build(L, mid); rootTree.R = Build(mid+1, R); rootTree.maxscore = Math.max(rootTree.L.maxscore, rootTree.R.maxscore); } return rootTree; } public int Query(Tree root, int LL, int RR) //查询 { int ret = 0; if (LL == root.ValueL && RR == root.ValueR) { return root.maxscore; } else { int mid; mid = (root.ValueL+root.ValueR)/2; if (RR <= mid) ret = Query(root.L, LL, RR); else if (LL > mid) ret = Query(root.R, LL, RR); else ret = Math.max(Query(root.L, LL, mid), Query(root.R, mid + 1, RR)); return ret; } } public int Update(Tree root, int RR, int value) { //更新 int ret = 0; int mid = (root.ValueL + root.ValueR)/2; if (RR == root.ValueL && RR == root.ValueR) { return root.maxscore = value; } if (RR <= mid) ret = Update(root.L, RR, value); else ret = Update(root.R, RR, value); root.maxscore= Math.max(root.maxscore,ret); return root.maxscore; } //中序遍历二叉线段树 private void printTree(Tree root) { if( root!= null ){ printTree( root.L); System.out.print("["+root.ValueL+","+root.ValueR+"] "); printTree( root.R ); } } } public static void main(String[] args) throws IOException { int n, m; int a, b; int i; IntervalTree iTree = new IntervalTree(); Tree rootTree; String cmd; Scanner cin = new Scanner(new BufferedInputStream(System.in)); while (cin.hasNext()) { n = cin.nextInt(); m = cin.nextInt(); for(i = 1; i<=n; i++) score[i] = cin.nextInt(); iTree.pos = 0; rootTree = iTree.Build(1, n); //iTree.printTree(rootTree); // System.out.println(); for(i = 0; i<m; i++) { cmd = cin.next(); a = cin.nextInt(); b = cin.nextInt(); if (cmd.equals("Q")) { if(a == b) System.out.println(score[a]); else System.out.println(iTree.Query(rootTree, a, b)); } else { score[a] = b; iTree.Update(rootTree, a, b); } } } } }
源码下载:
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2389北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1984import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1883POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1394接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2464当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1817关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1801关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1816关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1769一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2087POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2565设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2110继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2540继续上文http://128kj.iteye. ... -
AVL树及JAVA实现
2012-11-26 16:34 2283一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2058形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2848例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2125字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18694堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4042一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3328前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种树形结构,它将一个数组分割成多个小 区间,每个区间对应树上的一个节点。线段树的每个节点都包含了该...
hdu 1166线段树代码
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
标题与描述均提到了“hdu 1166线段树”,这表明文章的核心是关于线段树在解决特定问题中的应用。线段树是一种数据结构,主要用于处理区间查询和更新操作,尤其是在大规模数据集上。在本例中,通过分析给定的部分代码...
**案例1:Hdu1754 Ihateit** - **功能**: 单点替换与区间最值查询。 - **关键代码解析**: - **PushUp(int rt)**: 更新父节点的最大值。 - **build(int l, int r, int rt)**: 构建线段树,其中 `l` 和 `r` 表示...
### 线段树经典知识点解析 #### 一、线段树简介与代码风格 **线段树**是一种用于高效处理区间查询与更新操作的数据结构。它可以用来解决一系列与区间有关的问题,例如区间求和、区间最值等问题。相较于其他数据...
- **HDU 3074**:简单的线段树题目,要求求解区间乘积。在节点中维护区间乘积信息即可。 - **BZOJ 1798**:涉及到区间乘法和加法的操作,需要求解区间和。在线段树中需要支持这两种操作,并正确处理它们之间的关系...
**线段树(Segment Tree)**是一种用于处理区间查询和修改的高效数据结构。在这个问题中,线段树的每个节点存储的信息不仅仅是区间内的和,而是区间内不同数字的和。线段树的每个节点包含以下信息: 1. `a` 和 `b`...
这个压缩包包含了丰富的学习资料,旨在帮助参赛者提升编程技能,熟悉竞赛环境,以及掌握解决算法问题的策略。 课件内容可能涵盖以下几个核心部分: 1. **算法基础**:这部分通常会讲解基础的数据结构,如数组、...
2. **线段树**:线段树是一种数据结构,用于高效地处理区间查询和更新操作。它可以实时维护一个区间内的信息,如求和、最大值或最小值。线段树在处理动态区间问题时非常有效,如在数组上进行区间加法、区间求和等...
HDU入门代码(2000-2099)是一个专门为ACM(国际大学生程序设计竞赛,简称ICPC)初学者准备的资源集合。这个压缩包包含了从2000到2099编号的HDU(杭州电子科技大学在线评测系统)题目,每个题目都配有详细的解题报告...
**Dijkstra算法解HDU1874** Dijkstra算法是一种经典的图论算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出,主要用于解决单源最短路径问题。在这个问题中,我们需要从一个指定的起点(源节点)出发,找到...
3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、拓扑排序等)。 4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **...
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
HDU算法讲解的PPT是一份非常有价值的教育资源,由知名教育机构HDU(杭州电子科技大学)的lcy老师精心制作并讲解。这份PPT涵盖了算法的各个方面,是学习和提升算法能力的理想材料。标签“算法”、“讲解”和“经典”...
【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU...通过学习和实践这些知识点,不仅可以提高在HDU平台上的解题能力,也能为其他编程竞赛和实际项目开发打下坚实的基础。
总结来说,"二叉搜索树练习 HDU3791"是一道关于二叉搜索树操作的编程题,可能需要实现插入、删除、查找等基本操作,并通过分析`Main.java`源码来理解和解决问题。同时,可能需要借助各种工具进行调试和测试,以确保...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...