區(qū)間算法題用線段樹可以秒解？
背景
給一個(gè)兩個(gè)數(shù)組，其中一個(gè)數(shù)組是 A [1,2,3,4]，另外一個(gè)數(shù)組是 B [5,6,7,8]。讓你求兩個(gè)數(shù)組合并后的大數(shù)組的：
最大值 最小值 總和
這題是不是很簡單？我們直接可以很輕松地在 的時(shí)間解決，其中 m 和 n 分別為數(shù)組 A 和 B 的大小。
那如果我可以「修改」 A 和 B 的某些值，并且我要求「很多次」最大值，最小值和總和呢？
樸素的思路是原地修改數(shù)組，然后 的時(shí)間重新計(jì)算。顯然這并沒有利用之前計(jì)算好的結(jié)果，效率是不高的。那有沒有效率更高的做法？
有！線段樹就可以解決。
線段樹是什么？
線段樹本質(zhì)上就是一棵樹。更準(zhǔn)確地說，它是一顆二叉樹，而且它是一顆平衡二叉樹。關(guān)于為什么是平衡二叉樹，我們后面會(huì)講，這里大家先有這樣一個(gè)認(rèn)識(shí)。
雖然是一棵二叉樹，但是線段樹我們通常使用數(shù)組來模擬樹結(jié)構(gòu)，而不是傳統(tǒng)的定義 TreeNode 。
一方面是因?yàn)閷?shí)現(xiàn)起來容易，另外一方面是因?yàn)榫€段樹其實(shí)是一顆完全二叉樹，因此使用數(shù)組直接模擬會(huì)很高效。這里的原因我已經(jīng)在之前寫的堆專題中的二叉堆實(shí)現(xiàn)的時(shí)候中講過了，大家可以在我的公眾號(hào)《力扣加加》回復(fù)「堆」獲取。
線段樹解決什么問題？
正如它的名字，線段樹和線段（區(qū)間）有關(guān)。線段樹的每一個(gè)樹節(jié)點(diǎn)其實(shí)都存儲(chǔ)了一個(gè)「區(qū)間（段）的信息」。然后這些區(qū)間的信息如果「滿足一定的性質(zhì)」就可以用線段樹來提高性能。
那：
究竟是什么樣的性質(zhì)？ 如何提高的性能呢？
究竟是什么樣的性質(zhì)？
比如前面我們提到的最大值，最小值以及求和就滿足這個(gè)「一定性質(zhì)」。即我可以根據(jù)若干個(gè)（這里是兩個(gè)）子集推導(dǎo)出子集的并集的某一指標(biāo)。
以上面的例子來說，我們可以將數(shù)組 A 和 數(shù)組 B 看成兩個(gè)集合。那么：集合 A 的最大值和集合 B 的最大值已知，我們可以直接通過 max(Amax, Bmax) 求得集合 A 與集合 B 的并集的最大值。其中 Amax 和 Bmax 分別為集合 A 和集合 B 的最大值。最小值和總和也是一樣的，不再贅述。因此如果統(tǒng)計(jì)信息滿足這種性質(zhì)，我們就可以可以使用線段樹。但是要不要使用，還是要看用了線段樹后，是否能提高性能。
如何提高的性能呢？
關(guān)于提高性能，我先賣一個(gè)關(guān)子，等后面講完實(shí)現(xiàn)的時(shí)候，我們?cè)倭摹?/p>
實(shí)現(xiàn)
以文章開頭的求和為例。
我們可以將區(qū)間 A 和 區(qū)間 B 分別作為一個(gè)樹的左右節(jié)點(diǎn)，并將 A 的區(qū)間和與 B 的區(qū)間和分別存儲(chǔ)到左右子節(jié)點(diǎn)中。
接下來，將 A 的區(qū)間分為左右兩部分，同理 B 也分為左右兩部分。不斷執(zhí)行此過程直到無法繼續(xù)分。
總結(jié)一下就是將區(qū)間不斷一分為二，并將區(qū)間信息分別存儲(chǔ)到左右節(jié)點(diǎn)。如果是求和，那么區(qū)間信息就是區(qū)間的和。這個(gè)時(shí)候的線段樹大概是這樣的：
?藍(lán)色字體表示的區(qū)間和。
?
注意，這棵樹的所有葉子節(jié)點(diǎn)一共有 n 個(gè)（n 為原數(shù)組長度），并且每一個(gè)都對(duì)應(yīng)到原數(shù)組某一個(gè)值。
體現(xiàn)到代碼上也很容易。直接使用「后續(xù)遍歷」即可解決。這是因?yàn)椋覀冃枰雷笥夜?jié)點(diǎn)的統(tǒng)計(jì)信息，才能計(jì)算出當(dāng)前節(jié)點(diǎn)的統(tǒng)計(jì)信息。
?不熟悉后序遍歷的可以看下我之前的樹專題，公眾號(hào)力扣加加回復(fù)樹即可獲取
?
和二叉堆的表示方式一樣，我們可以用數(shù)組表示樹，用 2 * i + 1 和 2 * 1 + 2 來表示左右節(jié)點(diǎn)的索引，其中 i 為當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)在 tree 上的索引。
?tree 是用來構(gòu)建線段樹的數(shù)組，和二叉堆類似。只不過 tree[i] 目前存的是區(qū)間信息罷了。
?
上面我描述建樹的時(shí)候有明顯的遞歸性，因此我們可以遞歸的建樹。具體來說，可以定義一個(gè) build(tree_index, l, r) 方法 來建樹。其中 l 和 r 就是對(duì)應(yīng)區(qū)間的左右端點(diǎn)，這樣 l 和 r 就可以唯一確定一個(gè)區(qū)間。tree_index 其實(shí)是用來標(biāo)記當(dāng)前的區(qū)間信息應(yīng)該被更新到 tree 數(shù)組的哪個(gè)位置。
我們?cè)?tree 上存儲(chǔ)區(qū)間信息，那么最終就可以用 tree[tree_index] = .... 來更新區(qū)間信息啦。
核心代碼：
def?build(self,?tree_index:int,?l:int,?r:int):
????'''
????遞歸創(chuàng)建線段樹
????tree_index?:?線段樹節(jié)點(diǎn)在數(shù)組中位置
????l,?r?:?該節(jié)點(diǎn)表示的區(qū)間的左，右邊界
????'''
????if?l?==?r:
????????self.tree[tree_index]?=?self.data[l]
????????return
????mid?=?(l+r)?//?2?#?區(qū)間中點(diǎn)，對(duì)應(yīng)左孩子區(qū)間結(jié)束，右孩子區(qū)間開頭
????left,?right?=?2?*?tree_index?+?1,?2?*?tree_index?+?2?#?tree_index?的左右子樹索引
????self.build(left,?l,?mid)
????self.build(right,?mid+1,?r)
????#?典型的后序遍歷
????#?區(qū)間和使用加法即可，如果不是區(qū)間和要改下面這行代碼
????self.tree[tree_index]?=?self.tree[left]?+?self.tree[right]
上面代碼的數(shù)組 self.tree[i] 其實(shí)就是用來存類似上圖中藍(lán)色字體的區(qū)間和。「每一個(gè)區(qū)間都在 tree 上存有它一個(gè)位置，存它的區(qū)間和」。
「復(fù)雜度分析」
時(shí)間復(fù)雜度：由遞推關(guān)系式 T(n) = 2*T(n/2) + 1，因此時(shí)間復(fù)雜度為
?不知道怎么得出的 ? 可以看下我的《算法通關(guān)之路》的第一章內(nèi)容。https://leetcode-solution.cn/book-intro
?
空間復(fù)雜度：tree 的大小和 n 同階，因此空間復(fù)雜度為
終于把樹建好了，但是知道現(xiàn)在一點(diǎn)都沒有高效起來。我們要做的是高效處理「頻繁更新情況下的區(qū)間查詢」。
那基于這種線段樹的方法，如果更新和查詢區(qū)間信息如何做呢？
區(qū)間查詢
先回答簡單的問題「區(qū)間查詢」原理是什么。
如果查詢一個(gè)區(qū)間的信息。這里也是使用后序遍歷就 ok 了。比如我要找一個(gè)區(qū)間 [l,r] 的區(qū)間和。
那么如果當(dāng)前左節(jié)點(diǎn)：
完整地落在 [l,r] 內(nèi)。比如 [2,3] 完整地落在 [1,4] 內(nèi)。我們直接將 tree 中左節(jié)點(diǎn)對(duì)于的區(qū)間和取出來備用，不妨極為 lsum。 部分落在 [l,r] 內(nèi)。比如 [1,3] 部分落在 [2,4]。這個(gè)時(shí)候我們繼續(xù)遞歸，直到完整地落在區(qū)間內(nèi)（上面的那種情況），這個(gè)時(shí)候我們直接將 tree 中左節(jié)點(diǎn)對(duì)于的區(qū)間和取出來備用 將前面所有取出來備用的值加起來就是答案
右節(jié)點(diǎn)的處理也是一樣的，不再贅述。
「復(fù)雜度分析」
時(shí)間復(fù)雜度：查詢不需要在每個(gè)時(shí)刻都處理兩個(gè)葉子節(jié)點(diǎn)，實(shí)際上處理的次數(shù)大致和樹的高度一致。而樹是平衡的，因此復(fù)雜度為
或者由遞推關(guān)系式 T(n) = T(n/2) + 1，因此時(shí)間復(fù)雜度為
?不知道怎么得出的 ? 可以看下我的《算法通關(guān)之路》的第一章內(nèi)容。https://leetcode-solution.cn/book-intro
?
大家可以結(jié)合后面的代碼理解這個(gè)復(fù)雜度。
區(qū)間修改
那么如果我修改了 A[1] 為 1 呢？
如果不修改 tree，那么顯然查詢的區(qū)間只要包含了 A[1] 就一定是錯(cuò)的，比如查詢區(qū)間 [1,3] 的和 就會(huì)得到錯(cuò)誤的答案。因此我們要在修改了 A[1] 的時(shí)候同時(shí)去修改 tree。
問題在于「我們要修改哪些 tree 的值，修改為多少呢？」
首先回答第一個(gè)問題，修改哪些 tree 的值呢？
我們知道，線段樹的葉子節(jié)點(diǎn)都是原數(shù)組上的值，也是說，線段樹的 n 個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)的就是原數(shù)組。因此我們首先要「找到我們修改的位置對(duì)應(yīng)的那個(gè)葉子節(jié)點(diǎn)，將其值修改掉?！?/strong>
這就完了么？
沒有完。實(shí)際上，我們修改的葉子節(jié)點(diǎn)的所有父節(jié)點(diǎn)以及祖父節(jié)點(diǎn)（如果有的話）都需要改。也就是說我們需要「從這個(gè)葉子節(jié)點(diǎn)不斷冒泡到根節(jié)點(diǎn)，并修改沿途的區(qū)間信息」
?這個(gè)過程和瀏覽器的事件模型是類似的
?
接下來回答最后一個(gè)問題，具體修改為多少？
對(duì)于求和，我們需要首先將葉子節(jié)點(diǎn)改為修改后的值，另外所有葉子節(jié)點(diǎn)到根節(jié)點(diǎn)路徑上的點(diǎn)的區(qū)間和都加上 delta，其中 delta 就是改變前后的差值。
?求最大最小值如何更新？大家自己思考一下。
?
修改哪些節(jié)點(diǎn)，修改為多少的問題都解決了，那么代碼實(shí)現(xiàn)就容易了。
「復(fù)雜度分析」
時(shí)間復(fù)雜度：修改不需要在每個(gè)時(shí)刻都處理兩個(gè)葉子節(jié)點(diǎn)，實(shí)際上處理的次數(shù)大致和樹的高度一致。而樹是平衡的，因此復(fù)雜度為
或者由遞推關(guān)系式 T(n) = T(n/2) + 1，因此時(shí)間復(fù)雜度為
?不知道怎么得出的 ? 可以看下我的《算法通關(guān)之路》的第一章內(nèi)容。https://leetcode-solution.cn/book-intro
?
大家可以結(jié)合后面的代碼理解這個(gè)復(fù)雜度。
代碼
線段樹代碼已經(jīng)放在刷題插件上了，公眾號(hào)《力扣加加》回復(fù)插件即可獲取。
class?SegmentTree:
????def?__init__(self,?data:List[int]):
????????'''
????????data:?傳入的數(shù)組
????????'''
????????self.data?=?data
????????self.n?=?len(data)
????????#??申請(qǐng)?4?倍?data?長度的空間來存線段樹節(jié)點(diǎn)
????????self.tree?=?[None]?*?(4?*?self.n)?#?索引?i?的左孩子索引為?2i+1，右孩子為?2i+2
????????if?self.n:
????????????self.build(0,?0,?self.n-1)
????#?本質(zhì)就是一個(gè)自底向上的更新過程
????#?因此可以使用后序遍歷，即在函數(shù)返回的時(shí)候更新父節(jié)點(diǎn)。
????def?update(self,?tree_index,?l,?r,?index):
????????'''
????????tree_index:?某個(gè)根節(jié)點(diǎn)索引
????????l,?r?:?此根節(jié)點(diǎn)代表區(qū)間的左右邊界
????????index?:?更新的值的索引
????????'''
????????if?l?==?r==index?:
????????????self.tree[tree_index]?=?self.data[index]
????????????return
????????mid?=?(l+r)//2
????????left,?right?=?2?*?tree_index?+?1,?2?*?tree_index?+?2
????????if?index?>?mid:
????????????#?要更新的區(qū)間在右子樹
????????????self.update(right,?mid+1,?r,?index)
????????else:
????????????#?要更新的區(qū)間在左子樹?index<=mid
????????????self.update(left,?l,?mid,?index)
????????#?查詢區(qū)間一部分在左子樹一部分在右子樹
????????#?區(qū)間和使用加法即可，如果不是區(qū)間和要改下面這行代碼
????????self.tree[tree_index]?=?self.tree[left]?+?self.tree[right]
????def?updateSum(self,index:int,value:int):
????????self.data[index]?=?value
????????self.update(0,?0,?self.n-1,?index)
????def?query(self,?tree_index:int,?l:int,?r:int,?ql:int,?qr:int)?->?int:
????????'''
????????遞歸查詢區(qū)間?[ql,..,qr]?的值
????????tree_index?:?某個(gè)根節(jié)點(diǎn)的索引
????????l,?r?:?該節(jié)點(diǎn)表示的區(qū)間的左右邊界
????????ql,?qr:?待查詢區(qū)間的左右邊界
????????'''
????????if?l?==?ql?and?r?==?qr:
????????????return?self.tree[tree_index]
????????#?區(qū)間中點(diǎn)，對(duì)應(yīng)左孩子區(qū)間結(jié)束，右孩子區(qū)間開頭
????????mid?=?(l+r)?//?2
????????left,?right?=?tree_index?*?2?+?1,?tree_index?*?2?+?2
????????if?qr?<=?mid:
????????????#?查詢區(qū)間全在左子樹
????????????return?self.query(left,?l,?mid,?ql,?qr)
????????elif?ql?>?mid:
????????????#?查詢區(qū)間全在右子樹
????????????return?self.query(right,?mid+1,?r,?ql,?qr)
????????#?查詢區(qū)間一部分在左子樹一部分在右子樹
????????#?區(qū)間和使用加法即可，如果不是區(qū)間和要改下面這行代碼
????????return?self.query(left,?l,?mid,?ql,?mid)?+?self.query(right,?mid+1,?r,?mid+1,?qr)
????def?querySum(self,?ql:int,?qr:int)?->?int:
????????'''
????????返回區(qū)間?[ql,..,qr]?的和
????????'''
????????return?self.query(0,?0,?self.n-1,?ql,?qr)
????def?build(self,?tree_index:int,?l:int,?r:int):
????????'''
????????遞歸創(chuàng)建線段樹
????????tree_index?:?線段樹節(jié)點(diǎn)在數(shù)組中位置
????????l,?r?:?該節(jié)點(diǎn)表示的區(qū)間的左，右邊界
????????'''
????????if?l?==?r:
????????????self.tree[tree_index]?=?self.data[l]
????????????return
????????mid?=?(l+r)?//?2?#?區(qū)間中點(diǎn)，對(duì)應(yīng)左孩子區(qū)間結(jié)束，右孩子區(qū)間開頭
????????left,?right?=?2?*?tree_index?+?1,?2?*?tree_index?+?2?#?tree_index?的左右子樹索引
????????self.build(left,?l,?mid)
????????self.build(right,?mid+1,?r)
????????#?區(qū)間和使用加法即可，如果不是區(qū)間和要改下面這行代碼
????????self.tree[tree_index]?=?self.tree[left]?+?self.tree[right]
相關(guān)專題
堆
大家可以看下我之前寫的堆的專題的二叉堆實(shí)現(xiàn)。然后對(duì)比學(xué)習(xí)，順便還學(xué)了堆，豈不美哉？
樹狀數(shù)組
樹狀數(shù)組和線段樹類似，難度比線段樹稍微高一點(diǎn)點(diǎn)。有機(jī)會(huì)給大家寫一篇樹狀數(shù)組的文章。
immutablejs
前端的小伙伴應(yīng)該知道 immutable 吧？而 immutablejs 就是非常有名的實(shí)現(xiàn) immutable 的工具庫。西法之前寫過一篇 immutable 原理解析文章，感興趣的可以看下 https://lucifer.ren/blog/2020/06/13/immutable-js/
回答前面的問題
為啥是平衡二叉樹？
前面的時(shí)間復(fù)雜度其實(shí)也是基于樹是平衡二叉樹這一前提。那么線段樹一定是平衡二叉樹么？是的。這是因?yàn)榫€段樹是完全二叉樹，而完全二叉樹是平衡的。
當(dāng)然還有另外一個(gè)前提，那就是樹的總的節(jié)點(diǎn)數(shù)和原數(shù)組長度同階，也就是 n 的量級(jí)。關(guān)于為啥是同階的，也容易計(jì)算，只需要根據(jù)遞歸公式即可得出。
為啥線段樹能提高性能？
只要你理解了我「實(shí)現(xiàn)部分」的時(shí)間復(fù)雜度，那么就不難明白這個(gè)問題。因?yàn)樾薷暮筒樵兊臅r(shí)間復(fù)雜度都是 ，而不使用線段樹的暴力做法查詢的復(fù)雜度高達(dá) 。相應(yīng)的代價(jià)就是建樹的 的空間，因此線段樹也是一種典型的空間換時(shí)間算法。
最后點(diǎn)一下題。區(qū)間算法題是否可以用線段樹秒解？這其實(shí)文章中已經(jīng)回答過了，其取決于是否滿足兩點(diǎn)：
是否可以根據(jù)若干個(gè)（這里是兩個(gè)）子集推導(dǎo)出子集的并集的某一指標(biāo)。 是否能提高性能（相比于樸素的暴力解法）。通常面臨「頻繁修改」的場景都可以考慮使用線段樹「優(yōu)化修改后的查詢時(shí)間消耗」。
我的書 「《算法通關(guān)之路》」 已經(jīng)出版了，想要突破算法面試的朋友不要錯(cuò)過，京東淘寶當(dāng)當(dāng)亞馬遜等均有出售，電子版也有哦~
愛心三連擊
1.看到這里了就點(diǎn)個(gè)在看支持下吧，你的在看是我創(chuàng)作的動(dòng)力。
2.關(guān)注公眾號(hào)力扣加加，獲取更多算法硬核文章！加個(gè)星標(biāo)，不錯(cuò)過每一條成長的機(jī)會(huì)。
3.如果你覺得本文的內(nèi)容對(duì)你有幫助，就幫我轉(zhuǎn)發(fā)一下吧。
后臺(tái)回復(fù)：「電子書」，獲取我精心制作的算法刷題電子書（20+萬字） 后臺(tái)回復(fù)：「背包」，自動(dòng)獲取《背包九講》pdf 后臺(tái)回復(fù)：「腦圖」，自動(dòng)獲取我制作的算法腦圖總結(jié) 后臺(tái)回復(fù)：「刷題插件」，自動(dòng)獲取上萬人都在用的力扣刷題插件
另外你還可以回復(fù)具體的算法專題獲取相應(yīng)的文章，比如 「二分」，「堆」，「樹」，「鏈表」等等
微信更新了推送規(guī)則，優(yōu)先推送有互動(dòng)的公眾號(hào)，為了不錯(cuò)過更多優(yōu)質(zhì)文章，大家不妨點(diǎn)個(gè)贊！
