- 浏览: 601652 次
- 来自: ...
文章分类
最新评论
-
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 2396北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1987import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1899POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1397接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2468当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1828关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1821关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1819关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1773一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2104POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2578设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2123继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2709先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2295一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2063形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2851例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2136字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18708堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4045一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3331前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
在本篇博文中,我们将深入探讨线段树的概念,以及如何实现懒惰更新(Lazy Propagation)策略,同时结合POJ1823问题进行实战应用。懒惰更新是优化线段树性能的关键技巧,它避免了频繁地对每个节点进行更新,从而减少...
线段树的基本思想是将数组或序列分成多个部分(通常是二分),每个部分对应线段树的一个节点,通过节点间的合并操作,快速获取区间信息。 线段树的构建通常分为两个阶段:初始化和构造。初始化时,我们将原始数组中...
在本文中,我们将深入探讨“学习凸包(五):卷包裹算法——兼解POJ1113(JAVA)”这一主题。凸包是计算机图形学、算法和数据结构领域中的一个重要概念,它指的是在一组点集中,由这些点构成的最小外接多边形。在解决...
标题中的"POJ3468.zip_poj3468"显然与编程竞赛相关,POJ(Problemset Online Judge)是北京大学主办的一个在线编程竞赛平台,其中的3468是一个具体的题目编号。这个题目可能涉及到编程挑战,要求参赛者解决特定的...
标题中的"POJ3468.zip_ACM"暗示了这是一个与ACM(国际大学生程序设计竞赛)相关的项目。在ACM比赛中,参赛者需要解决各种算法问题,以提高编程和解决问题的能力。"POJ3468"是这个特定问题的编号,在编程竞赛平台上的...
标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...
标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...
在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...
### POJ 2352 Stars - 树状数组与线段树实现 #### 题目背景 POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
破解poj
在`poj2823.cpp`源代码中,我们可以看到实现线段树的具体细节,包括如何初始化、更新以及查询线段树。此外,代码可能还包括了问题的输入输出处理,错误检查,以及可能的优化策略,比如lazy propagation(惰性传播)...
用java的biginteger实现的poj1001,比较简单的方法
标题中的“使用字典树和Hashtable两种方法解POJ 2503”是指通过这两种数据结构解决一个特定的编程问题。POJ是Programming Online Judge的缩写,它是一个在线的编程竞赛平台,用户可以提交代码来解决特定的算法问题。...
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...
总结起来,"凸包练习: POJ 2187(JAVA)"是一个关于几何算法的实际应用问题,通过解决这个问题,你可以学习到如何用JAVA编程语言处理几何问题,掌握凸包算法,以及如何有效地读取、处理和输出数据。同时,这也是提升...
【北大POJ JAVA源码】是一系列用于解决北京大学在线编程平台(POJ)问题的Java程序集合。这个压缩包中的代码资源,对于学习Java编程、算法设计和优化以及熟悉在线编程竞赛有着重要的参考价值。POJ是北京大学面向全国...
标题中的“字典树练习 POJ 1056”是指一个编程问题,源自编程竞赛网站POJ(Programming Online Judge)的题目1056。POJ是一个在线平台,程序员可以在这里提交代码并测试其正确性,以解决给定的问题。这类问题通常...