[程式] Segment Tree (線段樹)

Segment Tree 是個用空間來交換時間的資料結構，特別適合用在搜尋次數極為龐大的時候。其所需的額外空間約為既有資料的兩倍 (空間複雜度是 O(N)!)，時間複雜度則為 O(log(N))。

資料結構的部分就請直接參考一開頭的連結，或者網路上搜尋都有很多，這邊就不再介紹。以下僅就實作部分略作說明：

首先考量到要支援 C++ 的既有型態以及使用者自定義的型態，所以一樣是採用 template 來處理型態問題。當然這種方法的老問題就是沒辦法確定該型態有哪些運算子可用，因此這邊就學 C++ 一些會用到比較運算的容器，預設會用到 operator< (程式中 CHOICE 設為 2 的範例)。

不過進一步考量到自定義型態的 operator< 可能希望預設用在其他演算法 (ex: sort，或是 heap 之類的)，而 segment tree 這邊要的其實不單是 "比較" 這樣的概念，而是希望根據左子樹與右子樹的數值做完某種 "運算" 後得到一個結果 (例如計算總合，參考 CHOICE 為 6 的範例)，這時候應該要提供一個方法讓使用者可以自定義這種行為。因此藉由第二個 template parameter 來讓使用者可以自行設定。(另一個範例：CHOICE 為 1)

當然，藉由這種方法 SegmentTree 本身使用上的彈性就大多了，不過這樣還是有一項不足之處：使用者其實也可以為自定義型態提供 operator() 使其變為具有 function 特性的 functor，這樣就無須另外寫一個 struct 或 class (參考 CHOICE 為 3 的範例)。

綜合以上，我們就可以寫出一個相當具有彈性的資料結構，不過這邊有個小麻煩：當使用者自定義型態同時多載 (overload) 了 operator< 跟 operator() 該怎麼辦呢？這邊我的選擇是採用 operator() 而非 operator<，理由相當簡單：operator() 比起 operator< 更加貼近原本的意思。因此，我們必須提供一個方法去檢查使用者是否有提供 operator()，如果有的話則優先選用 operator()；反之，則選用預設的 operator<。

要達成上述的要求，這邊利用的是 C++ template 的一個概念：SFINAE (substitution failure is not an error)，可以參考程式碼的第 25 ~ 82 行，其中 struct has_function 就是利用 SFINAE 的主軸，根據給定的型態是否有 operator() 可以讓 has_function 的成員變數 value 分別為 true 或 false。而後續的 struct DefaultSegTreeOp 就可以利用 has_function 來判斷究竟有沒有 operator() 可以用。SFINAE 的概念也可以參考我以前寫過的這篇，有另一個針對 primitive type 跟 container type 做區別的用法。

以下程式碼 (目前只有 query 跟 update，update 尚不支援一個區間，僅可更新單一節點)：