資訊專欄INFORMATION COLUMN
摘要：題目是要查詢到這個(gè)區(qū)間內(nèi)某一點(diǎn)的。值是從最底層的子節(jié)點(diǎn)值里取最大值。因此，不用太復(fù)雜，遞歸就可以了。與所不同的是，對(duì)所給區(qū)間內(nèi)的元素個(gè)數(shù)求和，而非篩選。這樣就會(huì)出現(xiàn)的情況，視作本身處理。
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這個(gè)區(qū)間內(nèi)某一點(diǎn)的max。max值是從最底層的子節(jié)點(diǎn)max值里取最大值。因此，不用太復(fù)雜，遞歸就可以了。
Solutionpublic 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對(duì)所給區(qū)間內(nèi)的元素個(gè)數(shù)求和，而非篩選。這樣就會(huì)出現(xiàn)start <= root.start && end >= root.end的情況，視作root本身處理。
Solutionpublic 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);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66189.html
摘要：唯一需要注意的就是的賦值取左右子樹的的較大值，最后一層的獨(dú)立結(jié)點(diǎn)的為對(duì)應(yīng)數(shù)組中的值。 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...
摘要：和其它題目一樣，依然是遞歸的做法。注意若樹的結(jié)點(diǎn)范圍為，那么至少有個(gè)數(shù)在左子樹上，所以語(yǔ)句里用了號(hào)。另外，最后一句是調(diào)用遞歸之后的結(jié)果，必須寫在最后面。 Problem For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this nodes i...
摘要：這道題目是篩選出數(shù)組中的最小值，存入新數(shù)組。因此，聯(lián)想到和系列的題目，對(duì)于的處理，使用線段樹是非常有效的方法。之前我們創(chuàng)建的線段樹，有和兩個(gè)。參照這個(gè)參數(shù)，可以考慮在這道題增加一個(gè)的參數(shù)，代表每個(gè)結(jié)點(diǎn)的最小值。 Problem Given an integer array (index from 0 to n-1, where n is the size of this array),...
摘要：示例解題代碼注意，如果要在上提交解答，必須把接口和類的代碼一并提交，這里并沒有在寫類中 我理解的數(shù)據(jù)結(jié)構(gòu)（八）—— 線段樹（SegmentTree） 一、什么是線段樹 1.最經(jīng)典的線段樹問題：區(qū)間染色有一面墻，長(zhǎng)度為n，每次選擇一段墻進(jìn)行染色，m次操作后，我們可以看見多少種顏色？m次操作后，我們可以在[i, j]區(qū)間內(nèi)看見多少種顏色？showImg(https://segmentfau...
摘要：示例解題代碼注意，如果要在上提交解答，必須把接口和類的代碼一并提交，這里并沒有在寫類中 我理解的數(shù)據(jù)結(jié)構(gòu)（八）—— 線段樹（SegmentTree） 一、什么是線段樹 1.最經(jīng)典的線段樹問題：區(qū)間染色有一面墻，長(zhǎng)度為n，每次選擇一段墻進(jìn)行染色，m次操作后，我們可以看見多少種顏色？m次操作后，我們可以在[i, j]區(qū)間內(nèi)看見多少種顏色？showImg(https://segmentfau...
閱讀 1133·2021-11-24 10:21
閱讀 2573·2021-11-19 11:35
閱讀 1673·2019-08-30 15:55
閱讀 1301·2019-08-30 15:54
閱讀 1203·2019-08-30 15:53
閱讀 3513·2019-08-29 17:21
閱讀 3314·2019-08-29 16:12
閱讀 3424·2019-08-29 15:23
