客戶端基本不用的算法：線段樹實戰要點
- 2019 年 12 月 19 日
- 筆記
在上一公眾號中《線段樹基礎與 RMQ 問題》，通過區間和的問題場景，已經學習了線段樹的基本結構，以及其單點更新和區間查詢的操作。但是在解 《LeetCode-307 區域和檢索 – 數組可修改》 這道題目的時候，並不是一帆風順的。所以這一篇文章我們來討論一下線段樹在做題時會遇到的一些坑。
空間退化問題
在 《LeetCode-307 區域和檢索 – 數組可修改》[1] 中，我們會遇到下標索引超出範圍的 9/10 的 case。這也就是我們遇到的第一個最直觀的坑。
上文我們說過，線段樹是一棵完美二叉樹(Perfect Binary Tree)，可是題目中給出的結點個數不一定是 2 的 N 次冪個。所以，這就帶來了空間結構退化的問題。
這裡我們假設 N = 13 這個情況，然後我們通過之前的線段樹代碼進行代碼實現後其結構變成了這樣：
通過上圖，我們發現如果我們使用 2N = 26 的數組空間，實際上線段樹已經覆蓋了下標 31 ，這個場景下我們開 2N 的數組是不夠的。
這裡直接說結論：我們對線段樹的描述數組開 4N 的空間，是絕對夠用的。 具體的證明後續文章中單獨寫。
在談 RMQ 問題
在第一篇文章中，我們講了區間和的場景，將最重要的向上更新操作 Push Up 也做了介紹，並且給大家留了一道思考題：如何使用線段樹來實現 RMQ 問題。
其實我們只需要修改兩個地方：
- 在向上更新的時候，重新制定規則 – 父結點是兩個子節點的大值；
- 在查詢的時候，將結果取遞歸搜索的大值；
代碼如下：
// 吸取上面的教訓，現在我們數組開 4 倍 int tree[maxn << 2]; void push_up(int rt) { // 父結點是子節點中的最大值 tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]); } int query(int L, int R, int l, int r, int rt) { if (L <= l && r <= R) { return tree[rt]; } int m = (l + r) >> 1; int ret = 0; // 修改成遞歸查找區間最大值當做查詢結果 if (L <= m) ret = max(ret, query(L, R, l, m, rt << 1)); if (R > m) ret = max(ret, query(L, R, m + 1, r, rt << 1 | 1)); return ret; }
其實 RMQ 線段樹並沒有對線段樹結構有任何改變，僅僅是修改了父子結點間的運算規則。
這樣我們對於線段樹的理解又加深了一層，因為「線段」並不僅僅代表着一段的加和，延伸來看，其實對某一塊區間有着一定結果的運算規則，就可以使用線段樹結構來優化查詢和更新效率。
求解逆序數
這是一個很典型的統計場景，具體的題目是 《LeetCode-315 計算右側小於當前元素的個數》[2]，其實就是在大學時《線性代數》課程中的求逆序數。由於在課程題目中，每個數都是有規律的，所以我們根據通項公式或者遞推公式就可以求解。但是這道題目是給我們一個任意的數組，不存在數列所具有的特殊性，所以我們只能通過統計的效率來解決這個問題。
逆序數的簡單介紹：假設我們有這樣一組數
[2, 4, 3, 5, 1]，它有 5 個逆序對，分別是(2, 1)、(4, 3)、(4, 1)、(3, 1)、(5, 1)，我們要求的答案是，以每個數為首位逆序數的個數，例如上述這組需要輸出[1, 2, 1, 1, 0]。
這種題我們應該如何考慮呢？我們換一個角度考慮，假設我們有一個以正整數範圍的空線段樹，仍舊是區間和線段樹，這棵樹的每一個葉子結點記錄的是當前下標數字出現的次數。
我們需要的操作仍舊是 單點更新 和 區間查詢。順着以下思路來考慮問題：
- 構建一個
[1, MAXN]範圍的線段樹，所有結點全部填 0。MAXN代表數組中數字的最大值； - 反向遍歷傳入的數組；
- 遍歷到
x的時候，對線段樹做一次query(1, x - 1)操作，來記錄有多少個比x小的數已經出現； - 對線段樹執行一次
update(x, num + 1)操作，讓線段樹更新x的計數，做加 1 操作； - 重複 3-4 操作，每次的
query結果就是最後數組中對應的每一個值。
如上面的動畫所示，Nums 的箭頭代表遍歷情況，Result 數組代表最終的返回結果，右邊的操作記錄是對線段樹的操作 Log。
離散化
在上面求解逆序對的題目中，其求解的情況是不完整的。因為我們將數組中的數字全部映射到了數組的下標中，但是數組中的每個數字的取值範圍是 [-2^31, 2^31] ，如果出現負數和零那就無法完成映射了（因為線段樹的下標都是正數）。在這種情況下我們要如何解決這個問題呢？
這裡給出這兩點思考方向：
- 雖然每個數字的取值範圍是
[-2^31, 2^31]，但是給定數組的長度不會超過50000； - 逆序對只是比較了兩個數的大小關係，而不用在意具體的數字是多少；
這兩點是不是可以理解成，如果我們將這 N 個數，根據大小關係，映射到 [1, 50000] 這個範圍內就可以解決問題了？
例如我們有這麼一組數 [-1, -5, 0, 12, 8]，我們先升序排序處理一下 [-5, -1, 0, 8, 12] ，然後做一個 Hash 來映射到整數範圍 {-5: 1, -1: 2, 0: 3, 8: 4, 12: 5}。通過 Hash 我們的數組變成了 [2, 1, 3, 5, 4] 。如此我們就可以繼續使用上面的思路來求解了。
是不是這個思路非常巧妙~ 其實這種區間問題只涉及到大小關係的時候，都可以通過這個方法進行數字映射，從而投影到我們可求解的區域內。這種思路就叫做離散化。所謂的離散化官方的定義就是：把無限空間中有限的個體映射到有限的空間中去，以此提高算法的時空效率。當我們對這類題目求解的時候，由於我們縮小了求解範圍，從而算法的時間常數和空間複雜度都會有所降低，所以離散化也是最容易想到的優化點之一。
希望大家學習了逆序場景以及離散化的優化思路，可以自行 AC 這道題。另外，《LeetCode-493 翻轉對》這個題目也可以通過這兩個思路來嘗試解決一下。
優美的 notonlysuccess 寫法
notonlysuccess 是一個 ACM-ICPC 的前輩（網絡號 id），因為他的線段樹代碼十分清晰且優雅，所以他的代碼經常作為各個參賽選手的模板代碼（雖然線段樹最後大家都能徒手寫出來）。具體何為優雅，下面放上 notonlysuccess 的線段數區間和的代碼（其實在我公眾號上，所有的代碼風格都是在模仿 notonlysuccess，Respect ！！）：
#include <cstdio> // 優雅點 1：參數宏定義 #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 55555; int sum[maxn << 2]; // 優雅點 2：PushUp 抽離 void PushUP(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void build(int l, int r, int rt) { if (l == r) { scanf("%d", &sum[rt]); return ; } // 優雅點 3：能用位運算就用位運算 int m = (l + r) >> 1; build(lson); build(rson); PushUP(rt); } void update(int p, int add, int l, int r, int rt) { if (l == r) { sum[rt] += add; return ; } int m = (l + r) >> 1; if (p <= m) update(p , add , lson); else update(p , add , rson); PushUP(rt); } int query(int L, int R, int l, int r, int rt) { if (L <= l && r <= R) { return sum[rt]; } int m = (l + r) >> 1; int ret = 0; if (L <= m) ret += query(L , R , lson); if (R > m) ret += query(L , R , rson); return ret; }
總結
這篇文章講述了在題目實戰中使用線段樹的一些技巧。包括：
- 數組上限大小；
- RMQ 線段樹實現方式；
- 逆序數使用線段樹的求解思路；
- 離散化的優化方法；
notonlysuccess版優雅線段樹模板；
學習了這篇文章，你可以求解以下 LeetCode 題目：
- LeetCode-307 區域和檢索 – 數組可修改
- LeetCode-315 計算右側小於當前元素的個數
- LeetCode-493 翻轉對[3]
最後你會發現 Hard 題有好多套路！不是難，而是你沒有掌握的知識！?
參考資料
[1]
《LeetCode-307 區域和檢索 – 數組可修改》: https://leetcode-cn.com/classic/problems/range-sum-query-mutable/description/
[2]
《LeetCode-315 計算右側小於當前元素的個數》: https://leetcode-cn.com/classic/problems/count-of-smaller-numbers-after-self/
[3]
LeetCode-493 翻轉對: https://leetcode-cn.com/classic/problems/reverse-pairs/description/
