- 浏览: 580603 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
继续上文http://128kj.iteye.com/blog/1738772:
在那里用链状结构实现了二叉线段树,下面程序使用一维数组以完全二叉树的方式来存储。
先看一维数组存储线段树到底需要开多大的数组,网上有一个计算程序:
运行:
C:\ex>java SegmentTree
请输入区间长度:
5
线段树构造完成, 共有9 节点,最后一个节点是: 9
请输入区间长度:
10
线段树构造完成, 共有19 节点,最后一个节点是: 25
请输入区间长度:
100000
线段树构造完成, 共有199999 节点,最后一个节点是: 262141
对下面的程序,数组开到300000就可以了。
例:POJ3468
大致题意:给出一个长度为n的整数序列。在这个序列上有两个操作。
其中:
“C a b c”表示区间[a,b]里的所有数都增加c。
“Q a b”表示求出区间[a,b]里的所有数的和。
思路: 线段树+lazy思想:
样例:
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15
下面是AC过的代码:
样例2:
10 22
1 2 3 4 5 6 7 8 9 10
Q 4 4
C 1 10 3
C 6 10 3
C 6 9 3
C 8 9 -100
C 7 9 3
C 7 10 3
C 1 10 3
Q 6 10
Q 6 9
Q 8 9
Q 7 9
Q 7 10
Q 1 10
Q 2 4
C 3 6 3
Q 9 9
Q 1 1
Q 5 5
Q 6 6
Q 7 7
Q 6 8
ans
4
-82
-104
-147
-122
-100
-37
27
-73
7
14
21
25
-28
源码下载:
在那里用链状结构实现了二叉线段树,下面程序使用一维数组以完全二叉树的方式来存储。
先看一维数组存储线段树到底需要开多大的数组,网上有一个计算程序:
import java.util.Scanner; /*线段树空间计算程序 Power By:Comzyh*/ class segment {//线段树节点 int b,e; } public class SegmentTree{//线段树,用数组实现 static int M=5000000; segment seg[]; int Nnode;//节点数 int LastNode;//最后一个节点 public SegmentTree(){ seg=new segment[M]; for(int i=0;i<M;i++) seg[i]=new segment(); } void build(int b, int e, int root){//构造线段树 Nnode++; if (root>LastNode) LastNode=root; seg[root].b=b; seg[root].e=e; if (b==e) return; int mid =(b+e)>>1; build(b,mid,root<<1); build(mid+1,e,(root<<1)+1); } public int getNnode(){ return Nnode; } public int getLastNode(){ return LastNode; } public static void main(String args[]){ Scanner in=new Scanner(System.in); int N; while (true){ System.out.printf("请输入区间长度:\n"); N=in.nextInt(); if (N==0) break; SegmentTree st=new SegmentTree(); st.build(1,N,1); System.out.printf("线段树构造完成, 共有%d 节点,最后一个节点是: %d\n",st.getNnode(),st.getLastNode()); //注意:节点个数总是2N-1 } } }
运行:
C:\ex>java SegmentTree
请输入区间长度:
5
线段树构造完成, 共有9 节点,最后一个节点是: 9
请输入区间长度:
10
线段树构造完成, 共有19 节点,最后一个节点是: 25
请输入区间长度:
100000
线段树构造完成, 共有199999 节点,最后一个节点是: 262141
对下面的程序,数组开到300000就可以了。
例:POJ3468
大致题意:给出一个长度为n的整数序列。在这个序列上有两个操作。
其中:
“C a b c”表示区间[a,b]里的所有数都增加c。
“Q a b”表示求出区间[a,b]里的所有数的和。
思路: 线段树+lazy思想:
样例:
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15
下面是AC过的代码:
import java.util.Scanner; import java.io.BufferedInputStream; class Tree{ //线段树节点 int l, r; long v, add; } public class Main{//数组实现的二叉线段树 static int N= 100005; Tree node[]=new Tree[N*3]; long sum[]; public Main(long[] sum){ this.sum=sum; for(int i=0;i<3*N;i++) node[i]=new Tree(); } public int L(int u){ return u << 1; } public int R(int u) { return u << 1 | 1 ; } public void build ( int u, int l, int r ) //建以r为根的线段树[l,r] { node[u].l = l; node[u].r = r; node[u].add = 0; node[u].v = sum[r] - sum[l-1]; if ( l == r ) return; int mid = ( l + r ) >> 1; build ( L(u), l, mid ); build ( R(u), mid+1, r ); } public void update ( int u, int l, int r, int val ) //更新 { if ( l == node[u].l && node[u].r == r ) { node[u].add += val; node[u].v += val * ( r - l + 1 ); return; } if ( node[u].add != 0 ) { node[L(u)].add += node[u].add; node[L(u)].v += node[u].add * ( node[L(u)].r - node[L(u)].l + 1 ); node[R(u)].add += node[u].add; node[R(u)].v += node[u].add * ( node[R(u)].r - node[R(u)].l + 1 ); node[u].add = 0; } int mid = ( node[u].l + node[u].r ) >> 1; if ( r <= mid ) update ( L(u), l, r, val ); else if ( l > mid ) update ( R(u), l, r, val ); else { update ( L(u), l, mid, val ); update ( R(u), mid+1, r, val ); } node[u].v = node[L(u)].v + node[R(u)].v; } public long query ( int u, int l, int r ) //查询 { if ( l == node[u].l && node[u].r == r ) return node[u].v; if ( node[u].add != 0 ) { node[L(u)].add += node[u].add; node[L(u)].v += node[u].add * ( node[L(u)].r - node[L(u)].l + 1 ); node[R(u)].add += node[u].add; node[R(u)].v += node[u].add * ( node[R(u)].r - node[R(u)].l + 1 ); node[u].add = 0; } int mid = ( node[u].l + node[u].r ) >> 1; // 计算左右子结点的分隔点 if ( r <= mid) return query ( L(u), l, r ); // 和左孩子有交集,考察左子结点 else if ( l > mid ) return query ( R(u), l, r ); // 和右孩子有交集,考察右子结点 else return query ( L(u), l, mid ) + query ( R(u), mid+1, r ); } public static void main(String args[]){ Scanner in = new Scanner(new BufferedInputStream(System.in)); int n = in.nextInt(); int m = in.nextInt(); long[] sum=new long[n+1]; for(int i = 1; i<=n; i++){ sum[i] = sum[i-1] + in.nextInt(); } Main st=new Main(sum); st.build(1,1,n); //st.printTree(1); String cmd; int x; int y; int c; for(int i = 0; i<m; i++) { cmd = in.next(); if (cmd.equals("Q")) { x = in.nextInt(); y = in.nextInt(); System.out.println(st.query(1,x, y)); } else { x = in.nextInt(); y = in.nextInt(); c=in.nextInt(); // System.out.println("c="+c); st.update(1,x,y,c); } } } }
样例2:
10 22
1 2 3 4 5 6 7 8 9 10
Q 4 4
C 1 10 3
C 6 10 3
C 6 9 3
C 8 9 -100
C 7 9 3
C 7 10 3
C 1 10 3
Q 6 10
Q 6 9
Q 8 9
Q 7 9
Q 7 10
Q 1 10
Q 2 4
C 3 6 3
Q 9 9
Q 1 1
Q 5 5
Q 6 6
Q 7 7
Q 6 8
ans
4
-82
-104
-147
-122
-100
-37
27
-73
7
14
21
25
-28
源码下载:
发表评论
-
求二叉树上任意两个节点的最近公共父节点
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 2008POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2464设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2024继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2586先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2200一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 1995形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2773例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2052字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18540堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3972一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3259前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1739733
POJ3468,线段树处理,注意longlongint
破解poj
POJ 1328 java做!雷达问题!java版本!AC答案~
用java的biginteger实现的poj1001,比较简单的方法
NULL 博文链接:https://128kj.iteye.com/blog/1705139
NULL 博文链接:https://128kj.iteye.com/blog/1752345
树状数组解决区间操作_高效 对数组的某个区间进行两种操作:1)求和 2)每个数据加常数。要求:时间复杂度低
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1746750
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
POJ1048,加强版的约瑟夫问题 难度中等
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
北大poj JAVA源码
最外层(总树,设为第0层)右子树的根,内1层右子树的根,内2层右子树的根….内n层右子树的根,内n层左子树的根,内n-1层左子树的根……内1层左子树的根,最外层(总树,第0层)左子树的根。把总树的左子树作为新的...
NULL 博文链接:https://128kj.iteye.com/blog/1734586