【題目描述】
For an integer array (index from 0 to n-1, where n is the size of this array), in the corresponding Segment Tree, each node stores an extra attribute max to denote the maximum number in the interval of the array (index from start to end).
對(duì)于一個(gè)有n個(gè)數(shù)的整數(shù)數(shù)組，在對(duì)應(yīng)的線段樹(shù)中, 根節(jié)點(diǎn)所代表的區(qū)間為0-n-1, 每個(gè)節(jié)點(diǎn)有一個(gè)額外的屬性max，值為該節(jié)點(diǎn)所代表的數(shù)組區(qū)間start到end內(nèi)的最大值。
為Segment Tree設(shè)計(jì)一個(gè)query的方法，接受3個(gè)參數(shù)root,start和end，線段樹(shù)root所代表的數(shù)組中子區(qū)間[start, end]內(nèi)的最大值。
【注】在做此題之前，請(qǐng)先完成線段樹(shù)構(gòu)造這道題目。
【題目鏈接】
www.lintcode.com/en/problem/segment-tree-query/
【題目解析】
這應(yīng)該是Range Query的經(jīng)典題目之一了。
此題可用Segment Tree來(lái)做的。 Segment Tree線段樹(shù)每一個(gè)節(jié)點(diǎn)都是一段線段，有start和end，然后還可以有其他的值，比如區(qū)間和sum，區(qū)間最大值max，區(qū)間最小值min。我們可以用自底向上構(gòu)建二叉樹(shù)的方式構(gòu)建Segment Tree，這個(gè)過(guò)程也有點(diǎn)類(lèi)似于Bottom-up的merge sort，思想也是Divide and Conquer。完畢之后就可以在O(logn)的時(shí)間update，或者得到range Sum。
【參考答案】
