摘要:题目是要查询到这个区间内某一点的。值是从最底层的子节点值里取最大值。因此,不用太复杂,递归就可以了。与所不同的是,对所给区间内的元素个数求和,而非筛选。这样就会出现的情况,视作本身处理。
Segment Tree Query Problem
For an integer array (index from 0 to n-1, where n is the size of this array), in the corresponding SegmentTree, each node stores an extra attribute max to denote the maximum number in the interval of the array (index from start to end).
Design a query method with three parameters root, start and end, find the maximum number in the interval [start, end] by the given root of segment tree.
ExampleFor array [1, 4, 2, 3], the corresponding Segment Tree is:
</>复制代码
[0, 3, max=4]
/
[0,1,max=4] [2,3,max=3]
/ /
[0,0,max=1] [1,1,max=4] [2,2,max=2], [3,3,max=3]
query(root, 1, 1), return 4
query(root, 1, 2), return 4
query(root, 2, 3), return 3
query(root, 0, 2), return 4
Note题目是要查询start到end这个区间内某一点的max。max值是从最底层的子节点max值里取最大值。因此,不用太复杂,递归就可以了。
Solution</>复制代码
public class Solution {
public int query(SegmentTreeNode root, int start, int end) {
if (root == null || end < root.start || start > root.end) return 0;
if (root.start == root.end) return root.max;
return Math.max(query(root.left, start, end), query(root.right, start, end));
}
}
Segment Tree Query II
Problem
For an array, we can build a SegmentTree 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 SegmentTree.
ExampleFor array [0, 2, 3], the corresponding value Segment Tree is:
</>复制代码
[0, 3, count=3]
/
[0,1,count=1] [2,3,count=2]
/ /
[0,0,count=1] [1,1,count=0] [2,2,count=1], [3,3,count=1]
query(1, 1), return 0
query(1, 2), return 1
query(2, 3), return 2
query(0, 2), return 2
Note与Query I所不同的是,Query II对所给区间内的元素个数求和,而非筛选。这样就会出现start <= root.start && end >= root.end的情况,视作root本身处理。
Solution</>复制代码
public class Solution {
public int query(SegmentTreeNode root, int start, int end) {
if (root == null || start > root.end || end < root.start) return 0;
if (root.start == root.end || (start <= root.start && end >= root.end)) return root.count;
return query(root.left, start, end) + query(root.right, start, end);
}
}
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66189.html
摘要:唯一需要注意的就是的赋值取左右子树的的较大值,最后一层的独立结点的为对应数组中的值。 Segment Tree Build I Problem The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interv...
摘要:和其它题目一样,依然是递归的做法。注意若树的结点范围为,那么至少有个数在左子树上,所以语句里用了号。另外,最后一句是调用递归之后的结果,必须写在最后面。 Problem For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this nodes i...
摘要:这道题目是筛选出数组中的最小值,存入新数组。因此,联想到和系列的题目,对于的处理,使用线段树是非常有效的方法。之前我们创建的线段树,有和两个。参照这个参数,可以考虑在这道题增加一个的参数,代表每个结点的最小值。 Problem Given an integer array (index from 0 to n-1, where n is the size of this array),...
摘要:示例解题代码注意,如果要在上提交解答,必须把接口和类的代码一并提交,这里并没有在写类中 我理解的数据结构(八)—— 线段树(SegmentTree) 一、什么是线段树 1.最经典的线段树问题:区间染色有一面墙,长度为n,每次选择一段墙进行染色,m次操作后,我们可以看见多少种颜色?m次操作后,我们可以在[i, j]区间内看见多少种颜色?showImg(https://segmentfau...
摘要:示例解题代码注意,如果要在上提交解答,必须把接口和类的代码一并提交,这里并没有在写类中 我理解的数据结构(八)—— 线段树(SegmentTree) 一、什么是线段树 1.最经典的线段树问题:区间染色有一面墙,长度为n,每次选择一段墙进行染色,m次操作后,我们可以看见多少种颜色?m次操作后,我们可以在[i, j]区间内看见多少种颜色?showImg(https://segmentfau...
阅读 1130·2021-11-24 10:21
阅读 2568·2021-11-19 11:35
阅读 1666·2019-08-30 15:55
阅读 1297·2019-08-30 15:54
阅读 1197·2019-08-30 15:53
阅读 3508·2019-08-29 17:21
阅读 3312·2019-08-29 16:12
阅读 3416·2019-08-29 15:23
极致性价比!云服务器续费无忧!
Tesla A100/A800、Tesla V100S等多种GPU云主机特惠2折起,不限台数,续费同价。
NVIDIA RTX 40系,高性价比推理显卡,满足AI应用场景需要。
乌兰察布+上海青浦,满足东推西训AI场景需要