线段树入门
对算法有兴趣的可以来看看 在自然数,且所有的数不大于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)
剩余39页未读,继续阅读
- 粉丝: 1
- 资源: 8
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 物模块模型代码,前往设计物模块所属
- Java面试手册,助力大家面试过五关斩六将,面试成功
- HITK0303MP-VB一款P-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- mybatis动态sql之xml增删改查批量操作示例EmpMapper.xml
- C/C++内存检测工具Sanitizers
- HITK0302MP-VB一款N-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- 宝塔批量建站工具,很优秀的宝塔管理工具,基于宝塔api
- HITK0204MP-VB一款N-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- azeryhgtfxhj
- 操作系统实验页面置换算法