- 浏览: 532344 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (231)
- 一个操作系统的实现 (20)
- 汇编(NASM) (12)
- Linux编程 (11)
- 项目管理 (4)
- 计算机网络 (8)
- 设计模式(抽象&封装) (17)
- 数据结构和算法 (32)
- java基础 (6)
- UML细节 (2)
- C/C++ (31)
- Windows (2)
- 乱七八糟 (13)
- MyLaB (6)
- 系统程序员-成长计划 (8)
- POJ部分题目 (10)
- 数学 (6)
- 分布式 & 云计算 (2)
- python (13)
- 面试 (1)
- 链接、装载与库 (11)
- java并行编程 (3)
- 数据库 (0)
- 体系结构 (3)
- C++ template / STL (4)
- Linux环境和脚本 (6)
最新评论
-
chuanwang66:
默默水塘 写道typedef void(*Fun)(void) ...
C++虚函数表(转) -
默默水塘:
typedef void(*Fun)(void);
C++虚函数表(转) -
lishaoqingmn:
写的很好,例子简单明了,将观察者模式都表达了出来。
这里是ja ...
观察者模式——Observer
参考文章:
《在一维数组中以完全二叉树方式存储线段树的空间分析》 http://comzyh.tk/blog/archives/479/
《线段树简介与简单应用》http://hi.baidu.com/etwge/blog/item/c6c2dff887d2eb909f514664.html
我们大家存储线段树的方式无非两种:
- 二叉链表
- 一维数组完全二叉树
二叉链表优点是节省空间,缺点是编程复杂度大,执行效率较低,空间复杂度为2N
在一维数组以完全二叉树方式存储线段树的编程复杂度小,执行效率较高,但浪费空间
长期以来,我和我校的OIer一直不知以一维方式存储线段树到底需要开多大的数组.今天正好有些闲暇的时间,写了个小程序,分析了下一维线段树在一维方式存储下到底需要占用多少空间.经本文所述方式计算约为4N
先来补习一下完全二叉树的相关知识:
完全二叉树在一维数组中这样表示:根节点为1,其左子树为2,右子树为3.
根节点为N,其左孩子为2N,右孩子为2N+1
具体实现方式可参考我的一篇题解
,这里使用的就是完全二叉树方式
像线段树这样区间长度并不一定是 的二叉树,其占用空间为 2的(最深线段的深度)次幂,就给线段树的空间占用造成了很大的不确定性.在我们学校,关于线段树的空间占用,说法大致有以下几种
- 极端保守的:10N
- 保守(我):5N
- 乐观:3N
- 极乐观:2N
然而大家写的是后大部分都是尽量多开,对于其空间占用一直没有定论,现在我来给个定论:
先上一幅图:
可以看到,空间复杂度其实是最好 ,最差是 ,最好情况出现在略小于 附近,最坏情况出现在略大于 附近,由此看来,我们以后存线段树大概需要开4N+100 的数组就可以了.
关于 ,思考一下代表总区间[1,L]的线段树需要多少个节点即可(tips: 不断二分,上限是一棵满二叉树; conclusion: 空间<2^0+2^1+...+2^(1+log(L-1))=4(L-1)-1 )
附线段树空间计算程序:
输入区间长度,他来告诉你要开多大数组.
/*注:这是一棵离散型的线段树*/ #include <iostream> //#include <cstdio> //#include <cstdlib> using namespace std; struct segment { int b,e; }; segment seg[5000000]; int N; //线段树对应的总区间长度1,2,...,N int Nnode; //线段树中一共有多少结点(这棵线段树基本上是平衡的二叉树,但不一定是完全二叉树) int LastNode; //线段树中最后一个结点的序号 void build(int b, int e, int s); int main(){ while (1){ printf("Please Enter Interval length 请输入区间长度:\n"); scanf("%d",&N); if (N==0)return 0; Nnode=0; LastNode=0; build(1,N,1); printf("Complete binary tree, has build %d Nodes ,the last node numbered %d\n %d 最后一个节点:%d\n",Nnode,LastNode,Nnode,LastNode); //system("pause"); } } void build(int b, int e, int s){ Nnode++; if (s>LastNode) LastNode=s; seg[s].b=b; seg[s].e=e; if (b==e) return; int mid =(b+e)>>1; build(b,mid,s<<1); build(mid+1,e,(s<<1)+1); }
附线段树空间占用分析程序(打表),上面那个图的表就是它计算出来的:
/*线段树空间分析程序 Power By:Comzyh*/ #include <iostream> #include <cstdio> #include <cstdlib> using namespace std; struct segment { int b,e; }; segment seg[5000000]; int N; int Nnode,LastNode; void build(int b, int e, int s); int main(){ freopen ("segmentCount.csv","w",stdout); int i=1; scanf("%d",&N); printf("区间长度,节点数,最后一个节点编号\n"); while (N-i>=0){ Nnode=0; LastNode=0; build(1,i,1); printf("%d,%d,%d\n",i,Nnode,LastNode); i++; } //system("pause"); } void build(int b, int e, int s){ Nnode++; if (s>LastNode) LastNode=s; seg[s].b=b; seg[s].e=e; if (b==e) return; int mid =(b+e)>>1; build(b,mid,s<<1); build(mid+1,e,(s<<1)+1); }
然后打了个表,可以用来查询线段树空间
区间长度 ,占用空间 1:1 2:3 3:5 4:7 5:9 6:13 7:13 8:15 9:17 10:25 10:25 20:57 30:61 40:121 50:125 60:125 70:225 80:249 90:249 100:253 200:509 300:1009 400:1021 500:1021 600:2033 700:2041 800:2045 900:2045 1000:2045 2000:4093 3000:8185 4000:8189 5000:16369 6000:16377 7000:16381 8000:16381 9000:32737 10000:32753 20000:65521 30000:65533 40000:131057 50000:131069 60000:131069 70000:262113 80000:262129 90000:262137 100000:262141 200000:524285 300000:1048561 400000:1048573 500000:1048573 600000:2097137 700000:2097145 800000:2097149 900000:2097149 1000000:2097149 2000000:4194301 3000000:8388601 4000000:8388605 5000000:16777201 6000000:16777209 7000000:16777213 8000000:16777213 9000000:33554401 10000000:33554417
发表评论
-
快排备忘
2013-10-26 11:27 544http://hi.baidu.com/pluto455988 ... -
LRU简单实现C++
2013-10-17 10:52 3968页面置换算法: 在地址映射过程中,若在页面中发现所要访问的页 ... -
二叉树相关
2013-10-04 17:40 687本节主要是为了写二叉树类型题目练手的代码,重点培养运用“指针 ... -
双指针策略(《编程之美》3.5 最短摘要生成)
2013-03-26 15:17 2221本文源自《编程之美》3.5 最短摘要生成一课。 ... -
K-MEDOIDS聚类算法
2012-12-04 21:18 1934k-medoids聚类算法 (wiki上讲得很清楚啊:) ) ... -
搜索(三)——回溯
2012-11-23 15:23 1022一、回溯 和 深度搜索 ... -
哈希Hash
2012-11-21 14:42 972要点一:哈希表长度 的确定是个两难的问题:太短则容 ... -
状态压缩DP
2012-11-14 20:27 724引例、 例1、 例2、 例3、 ... -
模拟退火
2012-10-28 16:34 1197引用:http://www.cnblogs.com/heaad ... -
计算几何(一)——基础算法
2012-07-12 21:07 1898待续 《计算几何资料》为提纲 1. (1) 有向线段 ... -
计算几何(二)——平面最近点对
2012-07-12 10:54 885参考资料: 为何这个问题采用分治法 http://blog ... -
气泡滚大——剔除线性数据中的杂质
2012-06-18 09:43 937这是一道Java的面试题,但是我总结了除了一种自称为“ ... -
深入理解二分查找(二、二分答案)
2012-04-29 16:24 7177二分答案 如果已知候选答案的范围[min,max ... -
P问题、NP问题和NPC问题
2012-04-25 16:36 1043这篇文章转自这里 ... -
RMQ(Range Minimum/Maximum Query)区间最值查询
2012-04-18 20:47 1540一、RMQ问题描述 和 几种解题思路 RMQ问题 (Rang ... -
后缀数组
2012-04-16 09:49 1488一、后缀数组 及其对应的名次数组 举例:S=&quo ... -
大整数运算(部分转载)
2012-04-12 21:36 1167待补充:“浮点数高精度运算” 参见这里==> ... -
单向链表相关
2012-04-10 16:42 952单向链表是微软笔试常考的,参考这里:http://www.c ... -
关键路径(AOE)
2012-04-10 08:05 1648前面这段话是引用别人的,后面代码是自己写的,有待完善: ... -
搜索(二)——双向BFS
2012-03-24 17:18 2996参考这篇文章,以下前 ...
相关推荐
几个方便理解的线段树例子··················
国家队论文——线段树,比较难 国家队论文——线段树 国家队论文——线段树,比较难 国家队论文——线段树
主要介绍线段树,并介绍其数据结构,还有相关的例题分析
手打了一份线段树代码,...使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。
包含线段树的应用,二分统计的示例,是ACM学习的好资料~
线段树(模板+例题——郭神) 私用,随意拿!
射线线段和角——小学数学教学PPT学习教案.pptx
统计的力量-zkw线段树 zkw的讲课ppt,线段树经典之作,内含一种采用堆式存储的zkw线段树及其使用方法
学习线段树很好的资料 希望能够对你有一定的帮助
一种简单的线段树的实现 ,基础功能比较完善
线段树和树状数组
一个讲述线段树的好资料,这里主要是程序部分,希望对广大成员能够有所帮助
浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计...
线段树、线段树啊、线段树,线段树啊、线段树
线段树是一种二叉搜索树,...使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。
线段树是一种二叉搜索树,...使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。
线段树是一棵二叉树,其结点是一条“线段”——[a,b],它的左儿子和右儿子分别是这条线段的左半段和右半段,即[a, (a+b)/2 ]和[(a+b)/2 ,b]。线段树的叶子结点是长度为1的单位线段[a,a+1]。下图就是一棵根为[1,10]...
线段树(二)
线段树ppt,线段树ppt,线段树ppt,树ppt,线段树ppt,线段树ppt,
权值线段树和主席树入门PPT,权值线段树,顾名思义就是记录权值的线段树,普通的线段树直接以坐标为l,r建树,而权值线段树是以大小来建树,树上寸的信息是该权值的数量,而通过建树时二分从小到大的性质,可以用这...