一、概念解析

這次來介紹一個數據結構 - 線段樹。

在平時刷題或是工作中，經常會遇到這么一個問題，“給定一個數組，求出數組某段區間的一些性質”。

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

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

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

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

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

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

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

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

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

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

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

情況一：節點區間包含查找區間。這種情況直接遞歸向下查找即可

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

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

情況四：節點區間相等于查找區間。直接返回答案

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

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

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

二、動畫描述

三、代碼實現

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){ //如果節點區間相等于查找區間，直接返回對應的值即可 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)?{ ????????????//?節點相交查找區間的情況 ????????????if?(end?>mid){ leftMax=query(root.left,start,mid); }//節點包含查找區間的情況 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 個節點，你可能會問這個 2n 是怎么得到的，思考這個問題可以從葉子節點出發，一共有 n 個葉子節點，構建操作是從上往下不斷二分，這樣保證了樹的平衡，因此所有節點個數就是 n + n/2 + n/4 + ... + 1 = 2n。

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

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