开发工具:
文件大小: 532kb
下载次数: 0
上传时间: 2013-01-14
详细说明： 对算法有兴趣的可以来看看 在自然数，且所有的数不大于30000的范围内讨论一个问题：现在已知n条线段，把端点依次输入告诉你，然后有m个询问，每个询问输入一个点，要求这个点在多少条线段上出现过； 最基本的解法当然就是读一个点，就把所有线段比一下，看看在不在线段中； 每次询问都要把n条线段查一次，那么m次询问，就要运算m*n次，复杂度就是O(m*n) 这道题m和n都是30000，那么计算量达到了10^9；而计算机1秒的计算量大约是10^8的数量级，所以这种方法无论怎么优化都是超时 因为n条线段是固定的，所以某种程度上说每次都把n条线段查一遍有大量的重复和浪费； 线段树就是可以解决这类问题的数据结构 举例说明：已知线段[2,5] [4,6] [0,7]；求点2,4,7分别出现了多少次 在[0,7]区间上建立一棵满二叉树：（为了和已知线段区别，用【】表示线段树中的线段） 【0,7】 / \ 【0,3】 【4,7】 / \ / \ 【0,1】 【2,3】 【4,5】 【6,7】 / \ / \ / \ / \ 【0,0】 【1,1】 【2,2】 【3,3】 【4,4】 【5,5】 【6,6】 【7,7】 每个节点用结构体： struct line { int left,right; // 左端点、右端点 int n; // 记录这条线段出现了多少次，默认为0 }a[16]; 和堆类似，满二叉树的性质决定a[i]的左儿子是a[2*i]、右儿子是a[2*i+1]; 然后对于已知的线段依次进行插入操作： 从树根开始调用递归函数insert // 要插入的线段的左端点和右端点、以及当前线段树中的某条线段 void insert(int s,int t,int step) ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
