[LintCode] Segment Tree Query I & Segment Tree

vibiu 發布于2019-08-14 16:22 / 2859人閱讀

摘要：題目是要查詢到這個區間內某一點的。值是從最底層的子節點值里取最大值。因此，不用太復雜，遞歸就可以了。與所不同的是，對所給區間內的元素個數求和，而非篩選。這樣就會出現的情況，視作本身處理。

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);
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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