[LintCode] Segment Tree Query I & Segment Tree

vibiu 发布于2019-08-14 16:22 / 2769人阅读

摘要：题目是要查询到这个区间内某一点的。值是从最底层的子节点值里取最大值。因此，不用太复杂，递归就可以了。与所不同的是，对所给区间内的元素个数求和，而非筛选。这样就会出现的情况，视作本身处理。

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.

Example

For 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.

Example

For 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

[LintCode] Segment Tree Build &amp; Segment Tree B

摘要：唯一需要注意的就是的赋值取左右子树的的较大值，最后一层的独立结点的为对应数组中的值。 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...

honhon 2019-08-14 15:14 评论0 收藏0
[LintCode] Segment Tree Modify

摘要：和其它题目一样，依然是递归的做法。注意若树的结点范围为，那么至少有个数在左子树上，所以语句里用了号。另外，最后一句是调用递归之后的结果，必须写在最后面。 Problem For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this nodes i...

CoffeX 2019-08-14 16:23 评论0 收藏0
[LintCode] Interval Minimum Number

摘要：这道题目是筛选出数组中的最小值，存入新数组。因此，联想到和系列的题目，对于的处理，使用线段树是非常有效的方法。之前我们创建的线段树，有和两个。参照这个参数，可以考虑在这道题增加一个的参数，代表每个结点的最小值。 Problem Given an integer array (index from 0 to n-1, where n is the size of this array),...

taowen 2019-08-14 16:23 评论0 收藏0
我理解的数据结构（八）—— 线段树（SegmentTree）

摘要：示例解题代码注意，如果要在上提交解答，必须把接口和类的代码一并提交，这里并没有在写类中我理解的数据结构（八）—— 线段树（SegmentTree）一、什么是线段树 1.最经典的线段树问题：区间染色有一面墙，长度为n，每次选择一段墙进行染色，m次操作后，我们可以看见多少种颜色？m次操作后，我们可以在[i, j]区间内看见多少种颜色？showImg(https://segmentfau...

waltr 2019-08-16 13:36 评论0 收藏0
我理解的数据结构（八）—— 线段树（SegmentTree）

摘要：示例解题代码注意，如果要在上提交解答，必须把接口和类的代码一并提交，这里并没有在写类中我理解的数据结构（八）—— 线段树（SegmentTree）一、什么是线段树 1.最经典的线段树问题：区间染色有一面墙，长度为n，每次选择一段墙进行染色，m次操作后，我们可以看见多少种颜色？m次操作后，我们可以在[i, j]区间内看见多少种颜色？showImg(https://segmentfau...

shaonbean 2019-07-01 10:54 评论0 收藏0