- 浏览: 580675 次
- 来自: ...
文章分类
最新评论
-
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 2319北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1939import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1822POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1342接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2406当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1754关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1646关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1738关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1684一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2009POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2465设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2024继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2484继续上文http://128kj.iteye. ... -
AVL树及JAVA实现
2012-11-26 16:34 2200一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 1996形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2773例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2052字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18542堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3972一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3259前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
hdu 1166线段树代码
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
hdu 1166线段树
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
NULL 博文链接:https://128kj.iteye.com/blog/1716470
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
涵盖注册、入门的十题答案,适合刚刚接触hdu的同学。
很适合ACM初学者的文档, 题目,代码,解体思路一应俱全
hdu 1574 passed sorce
很实用的算法讲解,hdu的lcy老师讲解,还不错!!
HDU的一题........HDU DP动态规