【题目描述】
For an array, we can build a Segment Tree for it, each node stores an extra attribute count to denote the number of elements in the the array which value is between interval start and end. (The array may not fully filled by elements)
Design a query method with three parameters root,start and end, find the number of elements in the in array's interval [start,end] by the given root of value Segment Tree.
Notice:It is much easier to understand this problem if you finished Segment Tree Build and Segment Tree Query first.
对于一个数组,我们可以对其建立一棵线段树, 每个结点存储一个额外的值count来代表这个结点所指代的数组区间内的元素个数. (数组中并不一定每个位置上都有元素)
实现一个query的方法,该方法接受三个参数root,start和end, 分别代表线段树的根节点和需要查询的区间,找到数组中在区间[start,end]内的元素个数。
【注】如果你完成了 Segment Tree Build 和 Segment Tree Query两道题,会更容易理解此题。
【题目链接】
www.lintcode.com/en/problem/segment-tree-query-ii/
【题目解析】
题目里的start end指的是数组的值的取值范围,count表示的是在这个取值范围之内有几个数字。
可以采用二分法解题。
如果root.start >= start && root.end <= end, 这就意味着这个root所包含的范围是我们要求解的一个范围的子范围,这个范围内的count值我们是要的,所以直接返回root。count
接下来进行二分。
mid = (start + end)/2;
如果mid 《start, 说明root节点的左半部分是不需要考虑的,因此调用 query(root.right, start, end);
如果 mid 》= end, 说明root节点的右侧的值全部比end要大,也不是我们需要考虑的范围,因此调用 query(root,left, start ,end)
最后,如果mid在start跟end之间,那么就需要分别统计 start~mid mid+1~ end范围的结果,然后加起来。
【参考答案】
www.jiuzhang.com/solutions/segment-tree-query-ii/
相关推荐
线段树详细讲义和实现(英文)
吉如一线段树~~~
Segment-Tree based Cost Aggregation for Stereo Matching 文章代码
My solution for some spoj problems
Segment-tree based cost aggregation for stereo matching with enhanced segmentation
一个线段树的ppt,里面主要讲了线段树,主席树,和树链剖分
版权声明:本文为CSDN博主「Alex_McAvoy」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。 ...目录【概述】【基础操作实现】1.建树1)思路2)实现2.单点查询1)思路2)实现3....
Segment Routing 思科原厂培训PPT L3/L2 , Traffic Engineering (TE) / Fast Reroute (FRR) services are offered over the MPLS backbone Complex protocol stacks Complex troubleshooting & operation
前端工程师面试
3 digit counter using 7segment
进制转换 这是学汇编语言时的一些程序 对初学者很有帮助
Laravel开发-segment 为Laravel编写的segment.com包装
PI SEGMENT项目的源代码
什么是Segment Routing、背景、实现原理、优势及应用
类似堆栈的实现(tree_based_segtree.h)适用于一维可迭代对象,并提供范围查询和推入/弹出操作。 基于节点的实现(node_based_segtree_nd.h)适用于N维可迭代对象,并提供范围查询和范围更新方法。 此实现很可能...
android 自定义segment 能运行的
比MPLS TE更好的技术 MPLS -SR PPT
使用IAR开发ADI的ADUC70XX系列单片机时,编译出现下面错误提示: Fatal Error[e72]: Segment FIQ_STACK must b
思科公司 segment Routing 技术详细介绍 Cisco Segment Routing introduce