【數(shù)據(jù)結(jié)構(gòu)】線段樹
老規(guī)矩，簡書 Makedown 兼容性差咳秉。附上 CSDN 的 【數(shù)據(jù)結(jié)構(gòu)】線段樹
問題
最后一次用到線段樹爽蝴，是在深圳老東家實(shí)習(xí)面試的時候春宣，Jason 問到我的一個問題（具體問題不記得了，大致意思）：
- 一個固定大小
n的有限數(shù)組x- action 1 : 可以隨時更新某個區(qū)間
[i, j]內(nèi)的元素- action 2 : 可以查詢某個區(qū)間
[i, j]內(nèi)的最大值或最小值
你應(yīng)該如何做衙熔？
簡單的解法 1 登颓？
普通數(shù)組形式存儲，額外空間消耗 红氯，總共空間復(fù)雜度
.
action 1 : 遍歷區(qū)間[i, j]框咙，進(jìn)行元素的更新，時間復(fù)雜度 .
action 2: 遍歷區(qū)間 [i, j]痢甘，查找最大值或最小值喇嘱，時間復(fù)雜度 .
顯然這種形式對于有大量查詢操作的情況下，耗時會很嚴(yán)重塞栅。
這時可以采用線段樹進(jìn)行處理者铜。
線段樹
時間復(fù)雜度和空間復(fù)雜度
需要預(yù)處理生成線段樹。
預(yù)處理耗時：
總共空間復(fù)雜度：
區(qū)間更新時間復(fù)雜度：
區(qū)間查詢時間復(fù)雜度：
創(chuàng)建線段樹
線段樹采用二叉樹形式存儲：
- 葉子節(jié)點(diǎn)對應(yīng)原始數(shù)組
x中的元素放椰。- 非葉子節(jié)點(diǎn)表示它所有子孫葉子節(jié)點(diǎn)所在區(qū)間的最值作烟。
假設(shè)數(shù)組 x 為：x = [ 2, 5, 1, 4, 9, 3 ] ，一共 n=6 個元素庄敛。
那么需要構(gòu)建的線段樹：
graph TD;
A(區(qū)間 0-5 min: 1)-->B;
A-->C;
B(區(qū)間 0-2 min: 1)-->D;
B-->E((1));
C(區(qū)間 3-5 min: 3)-->F;
C-->G((3));
D(區(qū)間 0-1 min: 2)-->H((2));
D-->I((5));
F(區(qū)間 3-4 min: 4)-->J((4));
F-->K((9));
注意構(gòu)建的時候俗壹，在非葉子節(jié)點(diǎn)更新你想要存儲的區(qū)間信息（區(qū)間最大值，區(qū)間最小值等）藻烤。
區(qū)間查詢
查詢 [1, 4] 內(nèi)的最小值
- 第一步：找到區(qū)間范圍內(nèi)的最下層節(jié)點(diǎn)：
graph TD;
A(區(qū)間 0-5 min: 1)-->B;
A-->C;
B(區(qū)間 0-2 min: 1)-->D;
B-->E((1 *));
C(區(qū)間 3-5 min: 3)-->F;
C-->G((3));
D(區(qū)間 0-1 min: 2)-->H((2));
D-->I((5 *));
F(區(qū)間 3-4 min: 4 *)-->J((4));
F-->K((9));
圖中標(biāo)記 * 號的節(jié)點(diǎn)為當(dāng)前需要查詢的節(jié)點(diǎn)绷雏。
為什么查詢的最下層是節(jié)點(diǎn)头滔？而不是葉子節(jié)點(diǎn)？（請注意看 [3, 4] 區(qū)間涎显，不需要查詢其葉子節(jié)點(diǎn)）
按道理每個區(qū)間范圍內(nèi)的葉子節(jié)點(diǎn)都需要更新坤检。
- 線段樹每個節(jié)點(diǎn)管理的都是一個區(qū)間（葉子節(jié)點(diǎn)管理的區(qū)間內(nèi)只有一個元素）
- 我們知道每個劃分出來的區(qū)間的最小值
- 如果區(qū)間查詢的范圍
[i, j]完全包含其中一個區(qū)間[ik, jk]（i <= ik <= jk <= j）- 顯然這個區(qū)間
[ik, jk]的最小值就是當(dāng)前值- 無需再繼續(xù)往下查詢
[1, 4] 區(qū)間包含的節(jié)點(diǎn)是：1-1, 2-2, 3-4。
- 第二步：遞歸向上查詢最小值
對應(yīng)的最小值分別為：x[1,1]=5, x[2,2]=1, x[3,4]=4
從上到下查找的過程（遞歸）示例期吓，用 xij 表示區(qū)間 x[i, j] 的值：
min(x14) = min(x12, x34)
= min(min(x11, x22), 4)
= min(min(5, 1), 4)
= min(1, 4)
= 1
區(qū)間更新
更新 [1, 4] 之間所有元素加 3早歇。
- 第一步：找到需要更新的最下層節(jié)點(diǎn)
graph TD;
A(區(qū)間 0-5 min: 1)-->B;
A-->C;
B(區(qū)間 0-2 min: 1)-->D;
B-->E((1 *));
C(區(qū)間 3-5 min: 3)-->F;
C-->G((3));
D(區(qū)間 0-1 min: 2)-->H((2));
D-->I((5 *));
F(區(qū)間 3-4 min: 4 *)-->J((4));
F-->K((9));
圖中標(biāo)記 * 號的節(jié)點(diǎn)為當(dāng)前需要更新的節(jié)點(diǎn)。
范圍同上讨勤。
同理：
- 我們知道每個區(qū)間的最小值
- 如果區(qū)間更新的范圍
[i, j]完全包含其中一個區(qū)間[ik, jk]（i <= ik <= jk <= j）- 顯然這個區(qū)間
[ik, jk]的最小值就是當(dāng)前值 + 變更值- 無須繼續(xù)向下更新
- 第二部：遞歸向上更新區(qū)間
遞歸往上更新后的結(jié)果為：
graph TD;
A(區(qū)間 0-5 min: 2 *)-->B;
A-->C;
B(區(qū)間 0-2 min: 2 *)-->D;
B-->E((4 *));
C(區(qū)間 3-5 min: 3 *)-->F;
C-->G((3));
D(區(qū)間 0-1 min: 2 *)-->H((2));
D-->I((8 *));
F(區(qū)間 3-4 min: 7 #)-->J((4));
F-->K((9));
圖中標(biāo)記 * 或 # 號的節(jié)點(diǎn)為更新過程中需要更新最小值的節(jié)點(diǎn)箭跳。
等等，是不是有點(diǎn)不對勁潭千？
還是 [3, 4] 這區(qū)間谱姓。[3, 4] 完全處于 [1, 4] 的更新范圍內(nèi)，在更新時無需更新其所有子節(jié)點(diǎn)刨晴。
但是按照上圖的結(jié)果屉来，如果我進(jìn)行查詢 [3, 3] 的最小值（或者更新值）。顯然結(jié)果與圖示的數(shù)據(jù)不符合狈癞。
所以需要增加更新標(biāo)志位茄靠，處理上面所提及的情況。
graph TD;
A(區(qū)間 0-5 min: 2)-->B;
A-->C;
B(區(qū)間 0-2 min: 2)-->D;
B-->E((4));
C(區(qū)間 3-5 min: 3)-->F;
C-->G((3));
D(區(qū)間 0-1 min: 2)-->H((2));
D-->I((8));
F(區(qū)間 3-4 min: 7 # +3)-->J((4));
F-->K((9));
該標(biāo)志位記錄當(dāng)前區(qū)間的變更值蝶桶。
在進(jìn)行涉及該區(qū)間的子節(jié)點(diǎn)查詢 / 更新時慨绳，需要取出該值遞歸更新沿途的區(qū)間。
查詢 [3, 3]
graph TD;
A(區(qū)間 0-5 min: 2)-->B;
A-->C;
B(區(qū)間 0-2 min: 2)-->D;
B-->E((4));
C(區(qū)間 3-5 min: 3)-->F;
C-->G((3));
D(區(qū)間 0-1 min: 2)-->H((2));
D-->I((8));
F(區(qū)間 3-4 min: 7 # 0)-->J((7 *));
F-->K((12 # +3));
其中 * 號為更新后的值莫瞬，# 號為傳遞的標(biāo)志位儡蔓。
在更新了區(qū)間后，需要把原有的 [3, 4] 標(biāo)志位清除（否則下次會導(dǎo)致重復(fù)更新）疼邀。
區(qū)間 [4, 5] 所有元素 -2
在查詢 [3, 3] 進(jìn)行這一步操作
graph TD;
A(區(qū)間 0-5 min: 2)-->B;
A-->C;
B(區(qū)間 0-2 min: 2)-->D;
B-->E((4));
C(區(qū)間 3-5 min: 3)-->F;
C-->G((3 *));
D(區(qū)間 0-1 min: 2)-->H((2));
D-->I((8));
F(區(qū)間 3-4 min: 7 # +3)-->J((4));
F-->K((9 *));
其中 * 號的為需要更新的最底層節(jié)點(diǎn)喂江。
graph TD;
A(區(qū)間 0-5 min: 2)-->B;
A-->C;
B(區(qū)間 0-2 min: 2)-->D;
B-->E((4));
C(區(qū)間 3-5 min: 3)-->F;
C-->G((3 -2 *));
D(區(qū)間 0-1 min: 2)-->H((2));
D-->I((8));
F(區(qū)間 3-4 min: 7 # 0)-->J((7 # +3));
F-->K((9 +3-2 *));
把區(qū)間標(biāo)志位和變更值一起傳遞（注意區(qū)間范圍），同時清除已經(jīng)更新完的區(qū)間標(biāo)志位旁振。
結(jié)果：
graph TD;
A(區(qū)間 0-5 min: 1)-->B;
A-->C;
B(區(qū)間 0-2 min: 2)-->D;
B-->E((4));
C(區(qū)間 3-5 min: 1)-->F;
C-->G((1));
D(區(qū)間 0-1 min: 2)-->H((2));
D-->I((8));
F(區(qū)間 3-4 min: 7)-->J((7));
F-->K((10));
