一、概念解析

這次來介紹一個數(shù)據(jù)結構 - 線段樹。

在平時刷題或是工作中，經(jīng)常會遇到這么一個問題，“給定一個數(shù)組，求出數(shù)組某段區(qū)間的一些性質(zhì)”。

比如給定一個數(shù)組 [5,2,6,1,-4,0,9,2]，讓你求出區(qū)間 [1,4] 上所有元素的和，在這個例子中，答案是 2 + 6 + 1 + (-4) = 5。

你可能會說，直接遍歷一遍不就好了嗎？

最簡單的方式就是直接遍歷一遍區(qū)間，時間復雜度也顯而易見 O(n)，如果在這個數(shù)組上頻繁進行這個操作，那么效率相對來說會比較低，怎么優(yōu)化呢？

對于求區(qū)間和的問題，前綴和數(shù)組是一個不錯的選擇，構建好前綴和數(shù)組后，求一個區(qū)間和的話只要前后一減就可以了，如果不算構建數(shù)組的時間，那么每次的操作時間復雜度就是 O(1)。

這里的問題在于前綴和數(shù)組只能解決求區(qū)間和的問題，但是其他的區(qū)間問題，前綴和數(shù)組并不能很好的解決，比如求某段區(qū)間上的最大值。

因此我們需要一個數(shù)據(jù)結構能夠幫助我們解決大部分數(shù)組的區(qū)間問題，而且時間復雜度要盡可能的低。

這也就是今天的主題 - 線段樹，首先要說明一點的是，線段樹也是二叉樹，只是它的節(jié)點里面含有區(qū)間的信息。

線段樹每個節(jié)點表示的是一個區(qū)間，每個節(jié)點將其表示的區(qū)間一分為二，左邊分到左子樹，右邊分到右子樹，根節(jié)點表示的是整個區(qū)間（也就是整個數(shù)組），葉子節(jié)點表示的是一個 index（也就是單個元素），因為每次對半分的緣故，線段樹構建出來是平衡的，也就是說樹的高度是 O(logn)，這里的 n 表示的是數(shù)組中所有的元素，這一點對于我們后面分析復雜度很重要。

線段樹有三個基本的操作，分別是構建線段樹(build)、區(qū)間查找(query)、還有就是修改(modify)，假設我們現(xiàn)在需要解決的問題是 “求區(qū)間上的最大值”，例子還是之前的例子，一起來看看怎么實現(xiàn)這些操作。

對于構建操作來說，相對簡單，你只需要記住 “自上而下而下遞歸分裂，自下而上回溯更新” 從根節(jié)點到葉子節(jié)點我們不斷地將區(qū)間一分為二，從葉子節(jié)點開始返回值，一直到根節(jié)點，不斷地更新區(qū)間信息。

查找操作是線段樹的核心操作，考慮的情況相對較多，這里有四種情況：

情況一：節(jié)點區(qū)間包含查找區(qū)間。這種情況直接遞歸向下查找即可

情況二：節(jié)點區(qū)間不相交于查找區(qū)間。因為沒有要查找的范圍，停止搜索

情況三：節(jié)點區(qū)間相交但不包含查找區(qū)間。將區(qū)間分成兩段，分別查找

情況四：節(jié)點區(qū)間相等于查找區(qū)間。直接返回答案

說明一下，這里說的 “包含” 的意思是一個區(qū)間全部元素都被另外一個區(qū)間涵蓋，“相交” 的意思是一個區(qū)間的部分元素被另外一個區(qū)間涵蓋，例如要查找的區(qū)間是 [1,3]，那么 [0,4] 包含要查找的區(qū)間，[2,5] 只是相交要查找的區(qū)間。對于區(qū)間查找，后面有圖解，跟著例子走一遍印象會更深刻。

最后一個修改操作，和構建操作類似，但有些許不同，你只需要記住 “自上而下遞歸查找，自下而上回溯更新”。修改的意思是，修改數(shù)組中的一個元素的值，這會影響相關的區(qū)間，相關的樹節(jié)點，因此，相關聯(lián)的節(jié)點也就需要更新。

線段樹靈活的地方在于，樹節(jié)點中存放的數(shù)據(jù)不同，它的功能就不同，比如說，你想要求解區(qū)間和，那么樹節(jié)點中就存放對應區(qū)間元素的和，你想求解區(qū)間上的最大值，那么樹節(jié)點中存放的就是對應區(qū)間上的最大值。不過話說回來，線段樹并不是一個被廣泛應用的數(shù)據(jù)結構，原因可能在于線段樹的構建和使用相對于前綴和數(shù)組這樣的技巧來說，稍微復雜了些。但是在解決數(shù)組區(qū)間的問題上，線段樹可以提供一個還不錯的思考方向。

二、動畫描述

三、代碼實現(xiàn)

publicclassSolution{ privateclassSegmentTreeNode{ intstart,end,max; SegmentTreeNodeleft,right; SegmentTreeNode(intstart,intend,intmax){ this.start=start; this.end=end; this.max=max; this.left=this.right=null; } } publicSegmentTreeNodebuild(intstart,intend,int[]nums){ if(start>end){ returnnull; } if(start==end){ returnnewSegmentTreeNode(start,end,nums[start]); } SegmentTreeNodenode=newSegmentTreeNode(start,end,nums[start]); //自上而下而下遞歸分裂 if(start!=end){ intmid=(start+end)/2; node.left=build(start,mid,nums); node.right=build(mid+1,end,nums); } //自下而上回溯更新 if(node.left!=null&&node.left.max>node.max){ node.max=node.left.max; } if(node.right!=null&&node.right.max>node.max){ node.max=node.right.max; } returnnode.max; } publicintquery(SegmentTreeNoderoot,intstart,intend){ //如果節(jié)點區(qū)間相等于查找區(qū)間，直接返回對應的值即可 if(root.start==start&&root.end==end){ returnroot.max; } intmid=(root.start+root.end)/2; intleftMax=Integer.MIN_VALUE,rightMax=Integer.MIN_VALUE; //判斷是否需要去左子樹查找 if(start<=?mid)?{ ????????????//?節(jié)點相交查找區(qū)間的情況 ????????????if?(end?>mid){ leftMax=query(root.left,start,mid); }//節(jié)點包含查找區(qū)間的情況 else{ leftMax=query(root.left,start,end); } } //判斷是否需要去右子樹查找 if(mid=root.end){ return; } //自上而下遞歸查找 modify(root.left,index,value); modify(root.right,index,value); //自下而上回溯更新 root.max=Math.max(root.left.max,root.right.max); } }

四、復雜度分析

三個操作中，構建樹的操作的時間復雜度是 O(n)，原因也很好解釋，構建的樹有 2n 個節(jié)點，你可能會問這個 2n 是怎么得到的，思考這個問題可以從葉子節(jié)點出發(fā)，一共有 n 個葉子節(jié)點，構建操作是從上往下不斷二分，這樣保證了樹的平衡，因此所有節(jié)點個數(shù)就是 n + n/2 + n/4 + ... + 1 = 2n。

由于構建每個節(jié)點只花了 O(1) 的時間，因此整個構建的時間復雜度就是 O(2n)，忽略常數(shù)項，也就是 O(n)。

修改和查找都是沿著一條或者幾條從上到下的路徑進行的，因為樹的高度是 O(logn)，所以這兩個操作的時間復雜度也是 O(logn)?？梢钥吹竭@個時間復雜度比暴力的 O(n) 還是快不少。