一、概念解析

這次來(lái)介紹一個(gè)數(shù)據(jù)結(jié)構(gòu) - 線(xiàn)段樹(shù)。

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

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

你可能會(huì)說(shuō)，直接遍歷一遍不就好了嗎？

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

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

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

因此我們需要一個(gè)數(shù)據(jù)結(jié)構(gòu)能夠幫助我們解決大部分?jǐn)?shù)組的區(qū)間問(wèn)題，而且時(shí)間復(fù)雜度要盡可能的低。

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

線(xiàn)段樹(shù)每個(gè)節(jié)點(diǎn)表示的是一個(gè)區(qū)間，每個(gè)節(jié)點(diǎn)將其表示的區(qū)間一分為二，左邊分到左子樹(shù)，右邊分到右子樹(shù)，根節(jié)點(diǎn)表示的是整個(gè)區(qū)間（也就是整個(gè)數(shù)組），葉子節(jié)點(diǎn)表示的是一個(gè) index（也就是單個(gè)元素），因?yàn)槊看螌?duì)半分的緣故，線(xiàn)段樹(shù)構(gòu)建出來(lái)是平衡的，也就是說(shuō)樹(shù)的高度是 O(logn)，這里的 n 表示的是數(shù)組中所有的元素，這一點(diǎn)對(duì)于我們后面分析復(fù)雜度很重要。

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

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

查找操作是線(xiàn)段樹(shù)的核心操作，考慮的情況相對(duì)較多，這里有四種情況：

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

情況二：節(jié)點(diǎn)區(qū)間不相交于查找區(qū)間。因?yàn)闆](méi)有要查找的范圍，停止搜索

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

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

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

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

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

二、動(dòng)畫(huà)描述

三、代碼實(shí)現(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é)點(diǎn)區(qū)間相等于查找區(qū)間，直接返回對(duì)應(yīng)的值即可 if(root.start==start&&root.end==end){ returnroot.max; } intmid=(root.start+root.end)/2; intleftMax=Integer.MIN_VALUE,rightMax=Integer.MIN_VALUE; //判斷是否需要去左子樹(shù)查找 if(start<=?mid)?{ ????????????//?節(jié)點(diǎn)相交查找區(qū)間的情況 ????????????if?(end?>mid){ leftMax=query(root.left,start,mid); }//節(jié)點(diǎn)包含查找區(qū)間的情況 else{ leftMax=query(root.left,start,end); } } //判斷是否需要去右子樹(shù)查找 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); } }

四、復(fù)雜度分析

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

由于構(gòu)建每個(gè)節(jié)點(diǎn)只花了 O(1) 的時(shí)間，因此整個(gè)構(gòu)建的時(shí)間復(fù)雜度就是 O(2n)，忽略常數(shù)項(xiàng)，也就是 O(n)。

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