本文主要介紹線段樹 (Segment Tree) 。
預備知識：樹狀數組 。
與樹狀數組 (Binary Index Tree, BIT, aka "二叉索引樹") 類似，線段樹适用于以下場景：
給定數組 <code>a[n]</code>， 并且要求 <code>w</code> 次修改數組，現有 <code>q</code> 次區間查詢，每次區間查詢包括 <code>[l, r]</code> 2 個參數，要求傳回 <code>sum(a[l, r])</code> 的值。
如果沒有「修改元素」的要求，顯然用字首和是最好的。既然樹狀數組能解決上述場景，那麼線段樹比樹狀數組好在哪裡呢？
線段樹可以在 \(O(\log{n})\) 的時間複雜度内實作單點修改、區間修改、區間查詢（區間求和，求區間最大值，求區間最小值）等操作。
樹狀數組适用于單點修改和區間查詢。
顯然，線段樹比樹狀數組能力更強，樹狀數組能做到的，線段樹同樣能做到。
線段樹的本質是一棵基于數組表示的二叉樹。
假設有一個大小為 5 的數組 \(a[5] = \{10, 11, 12, 13, 14\}\) ，記線段樹為 \(d[n]\) ，下标均從 1 開始計數。那麼該線段樹的形态如下：
每個節點表示一個區間（亦即所謂的「線段」），線段樹 \(d_i\) 記錄的是這一區間的和：
前面提到，線段樹的本質是基于數組表示的二叉樹，那麼節點 \(d_i\) 的左右孩子節點分别為 \(d_{2i}, d_{2i+1}\), 且根據線段樹的形态，那麼我們有：
\[d_i = d_{2i} + d_{2i+1}
\]
根據這一遞推公式，顯然可以得知，線段樹建立和修改是「自底向上」的。
建立線段樹的第一個問題：給定數組 \(a[n]\) ，那麼線段樹需要多大的空間？
分析 線段樹是一棵完全二叉樹，其高度為 \(h = \lceil \log{n} \rceil\)，高度從 0 開始計數，這意味着該二叉樹有 \(h+1\) 層。 考慮最壞情況，線段樹是一棵滿二叉樹，那麼有 \(2^{h+1} - 1\) 個節點。 \[2^{h+1} - 1 \le 2^{h+1} \le 2^{\log{n} + 2} \le 2^{\log{4n}} = 4n 是以，線段樹的空間一般開 \(4n\) 大小。當然，調數學庫精确算一下也是可以的 (if you want) 。
假設我們目前節點 \(d_i\) 表示的是區間 \([s, t]\) 之和，那麼其左節點 \(d_{2i}\) 表示的是區間 \([s,\frac{s+t}{2}]\) ，其右節點 \(d_{2i+1}\) 表示的是區間 \([\frac{s+t}{2}+1, t]\) .
建樹操作如下：
區間查詢，即求出區間 \([l,r]\) 之和，或者求出區間的最大值、最小值等操作。
依舊以這個樹為例子：
如果區間 \([l, r]\) 是線段樹上的一個節點，那麼這種查詢是簡單的，直接擷取 \(d_1 = 60\) 即可。那如果要查詢的區間不是對應于某個節點（即橫跨若幹節點），查詢是怎麼做到的呢？以查詢區間 \([3, 5]\) 為例，可以拆分為 \([3,3]\) 和 \([4, 5]\) 這 2 個節點。
一般地，查詢區間為 \([l, r]\) ，根據線段樹的性質，最多可拆分為 \(\log{n}\) 個子區間（這些子區間要求是一個極大的子區間，即 \([4,5]\) 不用再進一步拆分為 \([4,4]\) 和 \([5,5]\) ）。
如果要對 <code>nums[i]</code> 的值修改，那麼線段樹需要做出調整，任何包含 <code>nums[i]</code> 的區間都需要修改，複雜度是 \(O(\log{n})\) .
如果要對區間 \([a, b]\) 内數組元素做修改，顯然，線上段樹中，任何包括了 <code>nums[a ... b]</code> 中某一進制素的區間都要修改一次，這時候複雜度為 \(O((b-a+1) \cdot \log{n})\) ，這個複雜度屬實有點蚌埠住 ???? 。
是以需要引入「惰性标記」，簡單來說，就是空間換時間。
懶惰标記，簡單來說，就是通過延遲對節點資訊的更改，進而減少可能不必要的操作次數。每次執行修改時，我們通過打标記的方法表明該節點對應的區間在某一次操作中被更改，但不更新該節點的子節點的資訊。實質性的修改則在下一次通路帶有标記的節點時才進行。
如下圖所示，給線段樹的每個節點都加入一個标記值 <code>t[i]</code> ，表示這一區間的值的變化。
如果想要給區間 \([3,5]\) 的每個數都加上一個值 <code>val = 5</code> ，那麼會找到子區間 \([3,3]\) 和 \([4, 5]\) ，修改它們的标記值。注意，下圖的線段樹 <code>d[i]</code> 修改為節點的值（即區間之和）。
* 注：此處應為 <code>d[5] = 12 + 5 = 17, d[3] = 27 + 2 * 5 = 37</code>
雖然節點 <code>d[3]</code> 節點被修改，但它的孩子節點并沒有修改（所謂的「延遲更改」）。同時需要注意，<code>d[3]</code> 真正的變化值為 <code>5 * 2 = 10</code> .
接下來，如果我們需要查找區間 \([4,4]\) 之和，那麼會周遊到 \(d_3 = [3,4]\) 這一區間。當發現這一節點存在不為 0 的标記值時，此時需要真正地更新其孩子，将标記值「下放」，并重置标記值為 0 。
* 注：與上同理，此處應為 <code>d[5] = 17, d[3] = 37, d[6] = 18, d[7] = 19</code>
帶惰性标記的區間修改
帶惰性标記的區間查詢
模版例題：
洛谷 P3372
洛谷 P3373
[1] https://oi-wiki.org/ds/seg/
[2] javascript:void(0)