【題目描述】
For an array, we can build a Segment Tree 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 Segment Tree.
Notice：It is much easier to understand this problem if you finished?Segment Tree Build?and?Segment Tree Query?first.
對(duì)于一個(gè)數(shù)組，我們可以對(duì)其建立一棵線段樹, 每個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)額外的值count來代表這個(gè)結(jié)點(diǎn)所指代的數(shù)組區(qū)間內(nèi)的元素個(gè)數(shù). (數(shù)組中并不一定每個(gè)位置上都有元素)
實(shí)現(xiàn)一個(gè)query的方法合愈，該方法接受三個(gè)參數(shù)root,start和end, 分別代表線段樹的根節(jié)點(diǎn)和需要查詢的區(qū)間愕宋，找到數(shù)組中在區(qū)間[start,end]內(nèi)的元素個(gè)數(shù)强衡。
【注】如果你完成了?Segment Tree Build?和?Segment Tree Query兩道題，會(huì)更容易理解此題芳室。
【題目鏈接】
www.lintcode.com/en/problem/segment-tree-query-ii/
【題目解析】
題目里的start end指的是數(shù)組的值的取值范圍暖呕，count表示的是在這個(gè)取值范圍之內(nèi)有幾個(gè)數(shù)字旺入。
可以采用二分法解題挂签。
如果root.start >= start && root.end <= end, ?這就意味著這個(gè)root所包含的范圍是我們要求解的一個(gè)范圍的子范圍疤祭，這個(gè)范圍內(nèi)的count值我們是要的，所以直接返回root饵婆。count
接下來進(jìn)行二分勺馆。
mid = （start + end）／2；
如果mid 《start侨核， 說明root節(jié)點(diǎn)的左半部分是不需要考慮的草穆，因此調(diào)用 query（root.right, start, end）；
如果 mid 》= end搓译， 說明root節(jié)點(diǎn)的右側(cè)的值全部比end要大悲柱，也不是我們需要考慮的范圍，因此調(diào)用 query（root,left, start ,end）
最后些己，如果mid在start跟end之間豌鸡，那么就需要分別統(tǒng)計(jì) start～mid mid+1~ end范圍的結(jié)果，然后加起來段标。
【參考答案】
