2021 Week8 - Range Query

--- tags: 成大高階競技程式設計 2021 --- # 2021 Week8 - Range Query 註：:bulb: 代表相對少見、較進階或與主題關聯性較低的內容，讀者可自行斟酌觀看。 --- 之前我們透過前綴和（prefix sum）計算區間和，可是需要修改陣列元素時，複雜度為 $O(n)$，有沒有同時可以顧及修改與查詢效率的辦法呢？又或者要問區間最小值（RMQ, Range Minimum Query）呢？ > 回到之前分治的想法，如果問一個區間 $[l:r)$， > 我們把它對半拆成 $[l:m)$ 與 $[m:r)$ 有用嗎？ > 好像沒有，因為也不能比線性時間更快速地計算， > 那如果是像前綴和一樣利用預先算好的值呢？ > 好像也不行，畢竟我們不能事先知道 $[l:r)$， > 也就不能只算某些區間的值，讓不同的詢問都可以用。我們照著整個陣列的大小對半分開成二個子陣列， $[l:r)$ 中屬於左邊的與屬於右邊的就變成兩個子區間（子問題），這樣的**切分方式與每次詢問的區間沒有關係**，我們可以照著這個方式，左邊的左邊，左邊的右邊，右邊的左邊，右邊的右邊，一直將子區間切分。 > 想想原本計算量比較大的，是較大的區間，再切分後會發生什麼事？ > 很多子區間剛好是整個子陣列，因此線段樹就是提前計算這些子陣列的和。 --- # 基本線段樹（Basic Segment Tree）長度為 $6$ 的陣列建構而成的線段樹： ```graphviz digraph { n0 [shape=ellipse, label="[0:6)", fixedsize=true, width=1.0,height=0.5]; n1 [shape=ellipse, label="[0:3)", fixedsize=true, width=0.9,height=0.5]; n2 [shape=ellipse, label="[3:6)", fixedsize=true, width=0.9,height=0.5]; n3 [shape=ellipse, label="[0]", fixedsize=true, width=0.5,height=0.5]; n4 [shape=ellipse, label="[1:3)", fixedsize=true, width=0.8,height=0.5]; n5 [shape=ellipse, label="[3]", fixedsize=true, width=0.5,height=0.5]; n6 [shape=ellipse, label="[4:6)", fixedsize=true, width=0.8,height=0.5]; n9 [shape=ellipse, label="[1]", fixedsize=true, width=0.5,height=0.5]; n10 [shape=ellipse, label="[2]", fixedsize=true, width=0.5,height=0.5]; n13 [shape=ellipse, label="[4]", fixedsize=true, width=0.5,height=0.5]; n14 [shape=ellipse, label="[5]", fixedsize=true, width=0.5,height=0.5]; n0 -> n1; n0 -> n2; n1 -> n3; n1 -> n4; n2 -> n5; n2 -> n6; //n3 -> n7; //n3 -> n8; n4 -> n9; n4 -> n10; //n5 -> n11; //n5 -> n12; n6 -> n13; n6 -> n14; } ``` > 定義 $[l,r)\ in\ [b,e)$，代表在子陣列 $[b:e)$ 中，查詢的子區間為 $[l,r)$。 > > 假設要查詢 $[1:6)$，一開始問題是 $[1,6)\ in\ [0,6)$， > 分成 $[1,3)\ in\ [0,3)$ 與 $[3,6)\ in\ [3,6)$ 二個子問題， > $[1,3)\ in\ [0,3)$ 可以再切分，變成 $[1,3)\ in\ [1,3)$ ， > 接著把 $[1,3)$ 和 $[3,6)$ 二個子陣列事先算好的值加起來就是答案了。 <hr class="dashed"> ## 結構（Structure）先來分析一下線段樹的結構。 :::danger 長度為 $n$ 的陣列建構而成的線段樹，需要 **$2n-1$** 個節點。 ::: > 令集合 $S$ 中有若干個節點，所有陣列元素都恰好包含在一個節點之中； > 一開始 $S$ 中有 $n$ 個節點（樹葉），每個節點都包含一個陣列元素， > 每次我們將 $S$ 中的二個節點取出，合併成一個新節點，再放入 $S$ 中， > 經過 $n-1$ 次操作，$S$ 中就只剩下一個節點（樹根），包含所有陣列元素； > 因此除了原本的 $n$ 個節點以外，還有 $n-1$ 個新節點，總共 $2n-1$。 :::danger 長度為 $n$ 的陣列建構而成的線段樹，樹高為 **$\lceil \log_2n\rceil$**。 ::: > 陣列長度為 $n'$，會分長度為 $\lfloor \frac {n'}{2}\rfloor$ 與 $\lceil \frac {n'}{2}\rceil$ 的二個子陣列， > 如果一開始長度為 $n$，較長的一邊每次變為 $\lceil \frac {n'}{2}\rceil$，需要 $\lceil \log_2n\rceil$ 次才會變為 $1$。 <hr class="dashed"> ## 儲存（Storage） > 我們到底要怎麼儲存這個資料結構呢？ > 最簡單的方式就是透過指標（pointer）來儲存樹的邊， > 但這好像不是個好辦法，除了實作比較麻煩一點， > 整個樹狀結構也不會再改變，沒有必要用到指標。線段樹很接近完美二元樹（perfect binary tree），那就把它補齊，就可以進行編號了。 ```graphviz digraph { n0 [shape=ellipse, label="1", fixedsize=true, width=1.0,height=0.5]; n1 [shape=ellipse, label="2", fixedsize=true, width=0.9,height=0.5]; n2 [shape=ellipse, label="3", fixedsize=true, width=0.9,height=0.5]; n3 [shape=ellipse, label="4", fixedsize=true, width=0.5,height=0.5]; n4 [shape=ellipse, label="5", fixedsize=true, width=0.8,height=0.5]; n5 [shape=ellipse, label="6", fixedsize=true, width=0.5,height=0.5]; n6 [shape=ellipse, label="7", fixedsize=true, width=0.8,height=0.5]; n7 [shape=component, label="8", fixedsize=true, width=0.4,height=0.4]; n8 [shape=component, label="9", fixedsize=true, width=0.4,height=0.4]; n9 [shape=ellipse, label="10", fixedsize=true, width=0.5,height=0.5]; n10 [shape=ellipse, label="11", fixedsize=true, width=0.5,height=0.5]; n11 [shape=component, label="12", fixedsize=true, width=0.4,height=0.4]; n12 [shape=component, label="13", fixedsize=true, width=0.4,height=0.4]; n13 [shape=ellipse, label="14", fixedsize=true, width=0.5,height=0.5]; n14 [shape=ellipse, label="15", fixedsize=true, width=0.5,height=0.5]; n0 -> n1; n0 -> n2; n1 -> n3; n1 -> n4; n2 -> n5; n2 -> n6; n3 -> n7; n3 -> n8; n4 -> n9; n4 -> n10; n5 -> n11; n5 -> n12; n6 -> n13; n6 -> n14; } ``` :::danger 總共需要 $1+2+...+2^{\lceil \log_2n\rceil}=2^{\lceil \log_2n\rceil+1}-1\lt 4n$ 個節點。 ::: > 別忘記我們從 $1$ 開始編號，所以實際存放線段樹的陣列長度要再加一， > 當然也可以從 $0$ 開始編號。 > ~~不想算的話就直接開 $4n$ 的空間也可以~~ > > $2^{\lceil \log_2n\rceil}$ 就是第一個不小於 $n$ 的 $2$ 的冪。 > 將最左邊為 $1$ 的位元的右邊位元全部變成 $1$，最後再加一就是答案了。 > > ```cpp! > unsigned power2ceil(unsigned n) { > // smallest power of 2 >= n > n -= 1; > n |= n >> 1; > n |= n >> 2; > n |= n >> 4; > n |= n >> 8; > n |= n >> 16; > return n + 1; > } > ``` > > 概念如下，以 8 位元整數舉例。 > > ```graphviz > digraph { > rankdir=LR; > node [shape=record, style=filled]; > n0 [label="{0|0|0|1|?|?|?|?}"]; > n1 [label="{0|0|0|1|1|?|?|?}"]; > n2 [label="{0|0|0|1|1|1|1|?}"]; > n3 [label="{0|0|0|1|1|1|1|1}"]; > > edge [arrowhead=tee]; > n0 -> n1 -> n2 -> n3; > } > ``` > > 將第一個 $1$ 後的第一個位元變為 $1$，總共就有 $2$ 個 $1$ 了，再來是 $4$ 個，$8$ 個，以此類推。 <hr class="dashed"> ## 實作（Implementation） :::warning 給定一個長度為 $n$ 的整數陣列，需要支援二種操作： * 將第 $p$ 個元素改為 $x$ * 回答 $[l:r)$ 的區間和 ::: > 資料結構可以寫成一個類別（class）會比較好， > 當然要把資料都宣告成全域變數（global variables）， > 或是傳入一堆參數給函數也不是不行。 ```cpp! class SGT { int n; vector<long long> t; // tree int left(int tv) { return 2 * tv; } // left child of tv int right(int tv) { return 2 * tv + 1; } // right child of tv void build(const vector<long long>&, int, int, int); void set(int, long long, int, int, int); long long sum(int, int, int, int, int); public: SGT(const vector<long long>& v) : n{v.size()}, t(2 * power2ceil(n)) { build(v, 1, 0, n); } void set(int, long long); long long sum(int, int); }; ``` <hr class="dotted"> ## 建立（Build）先把陣列一直對半分開，等子陣列長度為 $1$ 時，就初始為對應的元素，之後遞迴返回之時，將子陣列的結果兩兩合併。 > * tv > * tree vertex > * 代表節點的編號 > * tl > * tree left > * 代表節點的子陣列的左邊界 > * tr > * tree right > * 代表節點的子陣列的右邊界 ```cpp! void SGT::build(const vector<long long>& v, int tv, int tl, int tr) { if (tr - tl == 1) t[tv] = v[tl]; else { int tm{(tl + tr) / 2}; build(v, left(tv), tl, tm); build(v, right(tv), tm, tr); t[tv] = t[left(tv)] + t[right(tv)]; } } ``` 每個節點都造訪一次，複雜度為 $O(n)$。 > ~~一般需要使用線段樹的題目，$O(n\log n)$ 的複雜度都是可以被接受的， > 不用寫 `build()`，直接用 `set()` 把每個元素初始化一次就好。~~ <hr class="dotted"> ## 單點修改（Modify） > 修改也可以是把某個元素加上一個值，做法都一樣。只需要更新與修改的元素有關的節點即可。 ```cpp! void SGT::set(int p, long long x, int tv, int tl, int tr) { if (tr - tl == 1) t[tv] = x; else { int tm{(tl + tr) / 2}; if (p < tm) set(p, x, left(tv), tl, tm); else set(p, x, right(tv), tm, tr); t[tv] = t[left(tv)] + t[right(tv)]; } } ``` 因為每一層只有造訪一個節點，複雜度跟樹高一樣，為 $O(\log n)$。 ```cpp! void SGT::set(int p, long long x) { set(p, x, 1, 0, n); } ``` <hr class="dotted"> ## 區間查詢（Range Query）如果子區間與子陣列相等，就不需要繼續切分了，直接回傳預先算好的值。 ```cpp! long long SGT::sum(int l, int r, int tv, int tl, int tr) { if (l == tl && r == tr) return t[tv]; int tm{(tl + tr) / 2}; if (r <= tm) return sum(l, r, left(tv), tl, tm); else if (l >= tm) return sum(l, r, right(tv), tm, tr); else return sum(l, tm, left(tv), tl, tm) + sum(tm, r, right(tv), tm, tr); } ``` 每一層最多造訪四個節點，複雜度為 $O(\log n)$。 > #### 證明 > 第一層只有樹根一個節點，命題為真； > 假設第 $k$ 層命題為真，第 $k$ 層被造訪的節點，只有最左以及最右的節點可以再往下遞迴 > （因為一開始整個區間是連續的，中間節點的子區間與子陣列必須相等）， > 因此第 $k+1$ 層最多就四個節點被造訪，命題也為真； > 根據數學歸納法，對任意層命題都為真。 ```cpp! long long SGT::sum(int l, int r) { return sum(l, r, 1, 0, n); } ``` <hr class="dashed"> ## 空間優化（Memory optimization）[^CPAlgo] 前面的編碼方式，在 $n$ 不是 $2$ 的冪時，會浪費一些空間，這邊透過不同的編碼方式，不管 $n$ 如何，都只需要 $2n-1$ 的空間。一開始說過，$n$ 個元素需要 $2n-1$ 個節點，因此右子樹編碼時，可以直接預留左子樹需要的空間，只需要改一下 `left()` 與 `right()` 即可。 ```cpp! SGT::left(int tv) { return tv + 1; } SGT::right(int tv, int tl, int tm) { return tv + 2 * (tm - tl); } ``` > 這樣的編碼就好像前序遍歷（pre-order traversal）。 ```graphviz digraph { n0 [shape=ellipse, label="1", fixedsize=true, width=1.0,height=0.5]; n1 [shape=ellipse, label="2", fixedsize=true, width=0.9,height=0.5]; n2 [shape=ellipse, label="7", fixedsize=true, width=0.9,height=0.5]; n3 [shape=ellipse, label="3", fixedsize=true, width=0.5,height=0.5]; n4 [shape=ellipse, label="4", fixedsize=true, width=0.8,height=0.5]; n5 [shape=ellipse, label="8", fixedsize=true, width=0.5,height=0.5]; n6 [shape=ellipse, label="9", fixedsize=true, width=0.8,height=0.5]; n9 [shape=ellipse, label="5", fixedsize=true, width=0.5,height=0.5]; n10 [shape=ellipse, label="6", fixedsize=true, width=0.5,height=0.5]; n13 [shape=ellipse, label="10", fixedsize=true, width=0.5,height=0.5]; n14 [shape=ellipse, label="11", fixedsize=true, width=0.5,height=0.5]; n0 -> n1; n0 -> n2; n1 -> n3; n1 -> n4; n2 -> n5; n2 -> n6; //n3 -> n7; //n3 -> n8; n4 -> n9; n4 -> n10; //n5 -> n11; //n5 -> n12; n6 -> n13; n6 -> n14; } ``` <hr class="dashed"> ## 適用問題除了求區間和，還有什麼區間查詢可以呢？ * sum * minimum / maximum * gcd * ... :::danger 任何符合結合律（Associative property）的函數都可以使用線段樹。 ::: 線段樹儲存的資料也不一定是整數，有可能是簡單的結構（struct）。 > 在 C++ 中，除了 `struct` 預設成員為公開，`struct` 與 `class` 基本上沒有差異； > 有些人會習慣把 `struct` 拿來用在一些很簡單的類別。 > 如果是事先寫好的程式碼，可以透過模板（template）， > 來實現泛型編程（Generic programming）， > 除了最基本的可以切換 `int` 與 `long long`， > 甚至是其它自己寫的結構，不過要有一些基本的運算子。 --- # 區間修改線段樹（Segment Tree with Range Modification） > 如果現在不只單點修改，而是區間修改呢？ > 區間內每個元素都要改變的話，就要線性時間了，但想想以下二種情況， > 第一種是修改了之後，某些部分根本沒有再被詢問到， > 第二種是修改了之後，在被詢問到之前，又被二次修改了， > 那這樣真的有必要馬上把全部的節點都更新嗎？如果整個子陣列都被做一樣的修改，我們「通常」可以知道整個子陣列的結果會如何變化，而這取決於修改函式與詢問函式是什麼。以修改函式是最簡單的賦值（assignment），詢問函式是最大值（maximum）為例，如果子陣列都改為 $x$ 的話，整個子陣列的最大值就是 $x$。 > 變更前的狀態： > > ```graphviz > digraph { > n0 [shape=ellipse, label="7,", fixedsize=true, width=1.0,height=0.5]; > n1 [shape=ellipse, label="7,", fixedsize=true, width=0.9,height=0.5]; > n2 [shape=ellipse, label="4,", fixedsize=true, width=0.9,height=0.5]; > n3 [shape=ellipse, label="5", fixedsize=true, width=0.5,height=0.5]; > n4 [shape=ellipse, label="7,", fixedsize=true, width=0.8,height=0.5]; > n5 [shape=ellipse, label="4", fixedsize=true, width=0.5,height=0.5]; > n6 [shape=ellipse, label="2,", fixedsize=true, width=0.8,height=0.5]; > n9 [shape=ellipse, label="7", fixedsize=true, width=0.5,height=0.5]; > n10 [shape=ellipse, label="3", fixedsize=true, width=0.5,height=0.5]; > n13 [shape=ellipse, label="1", fixedsize=true, width=0.5,height=0.5]; > n14 [shape=ellipse, label="2", fixedsize=true, width=0.5,height=0.5]; > > n0 -> n1; > n0 -> n2; > n1 -> n3; > n1 -> n4; > n2 -> n5; > n2 -> n6; > //n3 -> n7; > //n3 -> n8; > n4 -> n9; > n4 -> n10; > //n5 -> n11; > //n5 -> n12; > n6 -> n13; > n6 -> n14; > } > ``` > > 將 $[1:4)$ 改為 0，變更後的狀態： > > ```graphviz > digraph { > n0 [shape=ellipse, label="5,", fixedsize=true, width=1.0,height=0.5]; > n1 [shape=ellipse, label="5,", fixedsize=true, width=0.9,height=0.5]; > n2 [shape=ellipse, label="2,", fixedsize=true, width=0.9,height=0.5]; > n3 [shape=ellipse, label="5", fixedsize=true, width=0.5,height=0.5]; > n4 [shape=ellipse, label="0,0", fixedsize=true, width=0.8,height=0.5]; > n5 [shape=ellipse, label="0", fixedsize=true, width=0.5,height=0.5]; > n6 [shape=ellipse, label="2,", fixedsize=true, width=0.8,height=0.5]; > n9 [shape=ellipse, label="7", fixedsize=true, width=0.5,height=0.5]; > n10 [shape=ellipse, label="3", fixedsize=true, width=0.5,height=0.5]; > n13 [shape=ellipse, label="1", fixedsize=true, width=0.5,height=0.5]; > n14 [shape=ellipse, label="2", fixedsize=true, width=0.5,height=0.5]; > > n0 -> n1; > n0 -> n2; > n1 -> n3; > n1 -> n4; > n2 -> n5; > n2 -> n6; > //n3 -> n7; > //n3 -> n8; > n4 -> n9; > n4 -> n10; > //n5 -> n11; > //n5 -> n12; > n6 -> n13; > n6 -> n14; > } > ``` 這項技巧叫延遲傳遞（lazy propagation），當某個修改的子區間等於整個子陣列的話，我們就把整個子陣列的結果算好，並記錄還沒往下修改的值是什麼（因為下面的節點還沒更新），而暫時不去修改所有相關的節點。 > 這項技巧與寫入時複製（COW, Copy-on-write）的想法一樣， > **等到某件事真的需要被完成的時候，我們才去完成它。** <hr class=dashed> ## 實作（Implementation） :::warning 給定一個長度為 $n$ 的整數陣列，需要支援二種操作： * 將區間 $[l:r)$ 中的每個元素加上 $x$ * 回答 $[l:r)$ 的區間和 ::: > 修改函式是加（addition），詢問函式是和（sum） > 這邊就用空間優化的編碼方式吧， > 至於 `build()` 基本上一樣，就不寫了。我們現在需要多一個陣列 `lz`，紀錄尚未往下更新的值， > 這邊使用 `std::optional` 比較一般化（general），像是以這個問題為例， > 沒有值要往下更新的時候，可以設為 $0$ 就好，畢竟加上 $0$ 沒有任何影響， > 但如果修改函式是直接賦值的話，這樣就會有問題了。 ```cpp! template <typename value_t> class SGT { int n; vector<value_t> t; vector<optional<value_t>> lz; int left(int tv) { return tv + 1; } int right(int tv, int tl, int tm) { return tv + 2 * (tm - tl); } value_t merge(const value_t&, const value_t&); void update(int, int, const value_t&); void push(int, int, int); void modify(int, int, const value_t&, int, int, int); value_t query(int, int, int, int, int); public: explicit SGT(int _n) : n{_n}, t(2 * n), lz(2 * n) {} void modify(int l, int r, const value_t& x) { modify(l, r, x, 1, 0, n); } value_t query(int l, int r) { return query(l, r, 1, 0, n); } }; ``` <hr class=dotted> ## `merge()` 因為是查詢函式是和，自然就是回傳 `x + y`。 ```cpp! template <typename value_t> value_t SGT<value_t>::merge(const value_t& x, const value_t& y) { return x + y; } ``` <hr class=dotted> ## `update()` 當修改子區間與子陣列相等時，`update()` 會更新 `tv` 所在的節點，並記錄還沒有往下更新的值。因為每個元素都加上 `x`，整個子陣列的和自然就要加上 `len * x`。 > 有可能整個區間之前就被加過某個 $x'$ 了， > 記得不能把舊的值覆蓋掉，它們也還沒往下更新。 ```cpp! template <typename value_t> void SGT<value_t>::update(int tv, int len, const value_t& x) { if (!lz[tv]) lz[tv] = x; else lz[tv] = lz[tv].value() + x; t[tv] += len * x; } ``` <hr class=dotted> ## `push()` `push` 將儲存在 `lz` 中的值往下一層更新，並將 `lz` 初始。 ```cpp! template <typename value_t> void SGT<value_t>::push(int tv, int tl, int tr) { // lazy propagation if (!lz[tv]) return; int tm{(tl + tr) / 2}; update(left(tv), tm - tl, lz[tv].value()); update(right(tv, tl, tm), tr - tm, lz[tv].value()); lz[tv].reset(); } ``` <hr class=dotted> ## `modify()` 整個流程與查詢很像，如果子區間與子陣列相等，就透過 `update()` 去更新，否則就只能把要修改的子區間繼續拆分。既然要繼續造訪下層節點，那就必須把之前沒有更新的值，先更新好，才能繼續前進，因此透過 `push()` 把需要更新的值往下一層推進。 ```cpp! template <typename value_t> void SGT<value_t>::modify(int l, int r, const value_t& x, int tv, int tl, int tr) { if (l == tl && r == tr) update(tv, tr - tl, x); else { push(tv, tl, tr); int tm{(tl + tr) / 2}; if (r <= tm) modify(l, r, x, left(tv), tl, tm); else if (l >= tm) modify(l, r, x, right(tv, tl, tm), tm, tr); else modify(l, tm, x, left(tv), tl, tm), modify(tm, r, x, right(tv, tl, tm), tm, tr); t[tv] = merge(t[left(tv)], t[right(tv, tl, tm)]); } } ``` <hr class=dotted> ## `query()` **別忘了先把沒更新的值先往下更新**，其餘流程都一樣。 ```cpp! template <typename value_t> value_t SGT<value_t>::query(int l, int r, int tv, int tl, int tr) { if (l == tl && r == tr) return t[tv]; push(tv, tl, tr); int tm{(tl + tr) / 2}; if (r <= tm) return query(l, r, left(tv), tl, tm); else if (l >= tm) return query(l, r, right(tv, tl, tm), tm, tr); else return merge(query(l, tm, left(tv), tl, tm), query(tm, r, right(tv, tl, tm), tm, tr)); } ``` <hr class=dotted> **只有 `merge()` 跟 `update()` 會隨著不同的修改與查詢改變。** > 而像是修改函式是加，而詢問函式是最大公因數的話， > 就沒辦法透過延遲傳遞（lazy propagation）來快速進行。 :::spoiler 完整程式碼 ```cpp! // segment tree // range query & range modify template <typename value_t> class SGT { int n; vector<value_t> t; vector<optional<value_t>> lz; // [ tv+1 : tv+2*(tm-tl) ) -> left subtree int left(int tv) { return tv + 1; } int right(int tv, int tl, int tm) { return tv + 2 * (tm - tl); } /** differ from case to case **/ // query is "sum" and modify is "add" here value_t merge(const value_t& x, const value_t& y) { // associative function return x + y; } void update(int tv, int len, const value_t& x) { if (!lz[tv]) lz[tv] = x; else lz[tv] = lz[tv].value() + x; t[tv] += len * x; } /******************************/ void push(int tv, int tl, int tr) { // lazy propagation if (!lz[tv]) return; int tm{(tl + tr) / 2}; update(left(tv), tm - tl, lz[tv].value()); update(right(tv, tl, tm), tr - tm, lz[tv].value()); lz[tv].reset(); } void modify(int l, int r, const value_t& x, int tv, int tl, int tr) { if (l == tl && r == tr) update(tv, tr - tl, x); else { push(tv, tl, tr); int tm{(tl + tr) / 2}; if (r <= tm) modify(l, r, x, left(tv), tl, tm); else if (l >= tm) modify(l, r, x, right(tv, tl, tm), tm, tr); else modify(l, tm, x, left(tv), tl, tm), modify(tm, r, x, right(tv, tl, tm), tm, tr); t[tv] = merge(t[left(tv)], t[right(tv, tl, tm)]); } } value_t query(int l, int r, int tv, int tl, int tr) { if (l == tl && r == tr) return t[tv]; push(tv, tl, tr); int tm{(tl + tr) / 2}; if (r <= tm) return query(l, r, left(tv), tl, tm); else if (l >= tm) return query(l, r, right(tv, tl, tm), tm, tr); else return merge(query(l, tm, left(tv), tl, tm), query(tm, r, right(tv, tl, tm), tm, tr)); } public: explicit SGT(int _n) : n{_n}, t(2 * n), lz(2 * n) {} void modify(int l, int r, const value_t& x) { modify(l, r, x, 1, 0, n); } // [l:r) value_t query(int l, int r) { return query(l, r, 1, 0, n); } // [l:r) }; ``` ::: **記得要對哪邊操作，就把之前懶得更新的部分也先往下推進**，除此之外，區間修改線段樹與基本線段樹沒什麼差別，就看有沒有區間修改的需求。 --- # 極簡線段樹（Compact Segment Tree）[^EESGT]:bulb: > :bulb::bulb::bulb:[原文](https://codeforces.com/blog/entry/18051)稱之為「Efficient and easy segment trees」； > 中文圈也有提出類似（一樣？）的資料結構稱之為「zkw 線段樹」。陣列長度 $32$ 的線段樹，查詢區間為 $[5:29)$： ```graphviz digraph { SGT [shape=none, label= <<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="8" CELLPADDING="0"> <TR> <TD COLSPAN="64" BGCOLOR="Red"> 1: [0:32)</TD> </TR> <TR> <TD COLSPAN="32" BGCOLOR="Orange"> 2: [0:16)</TD> <TD COLSPAN="32"> 3: [16:32)</TD> </TR> <TR> <TD COLSPAN="16" BGCOLOR="Yellow"> 4: [0:8)</TD> <TD COLSPAN="16" SIDES="LT" BORDER="5"> 5: [8:16)</TD> <TD COLSPAN="16" SIDES="TR" BORDER="5"> 6: [16:24)</TD> <TD COLSPAN="16"> 7: [24:32)</TD> </TR> <TR> <TD COLSPAN="8" BGCOLOR="Green"> 8: [0:4)</TD> <TD COLSPAN="8"> 9: [4:8)</TD> <TD COLSPAN="8" SIDES="L" BORDER="5"> 10: [8:12)</TD> <TD COLSPAN="8" BORDER="0"> 11: [12:16)</TD> <TD COLSPAN="8" BORDER="0"> 12: [16:20)</TD> <TD COLSPAN="8" BORDER="0"> 13: [20:24)</TD> <TD COLSPAN="8" SIDES="TR" BORDER="5"> 14: [24:28)</TD> <TD COLSPAN="8"> 15: [28:32)</TD> </TR> <TR> <TD COLSPAN="4" BGCOLOR="Blue"> 16: [0:2)</TD> <TD COLSPAN="4"> 17: [2:4)</TD> <TD COLSPAN="4"> 18: [4:6)</TD> <TD COLSPAN="4" SIDES="LT" BORDER="5"> 19: [6:8)</TD> <TD COLSPAN="4" BORDER="0"> 20: [8:10)</TD> <TD COLSPAN="4" BORDER="0"> 21: [10:12)</TD> <TD COLSPAN="4" BORDER="0"> 22: [12:14)</TD> <TD COLSPAN="4" BORDER="0"> 23: [14:16)</TD> <TD COLSPAN="4" BORDER="0"> 24: [16:18)</TD> <TD COLSPAN="4" BORDER="0"> 25: [18:20)</TD> <TD COLSPAN="4" BORDER="0"> 26: [20:22)</TD> <TD COLSPAN="4" BORDER="0"> 27: [22:24)</TD> <TD COLSPAN="4" BORDER="0"> 28: [24:26)</TD> <TD COLSPAN="4" SIDES="R" BORDER="5"> 29: [26:28)</TD> <TD COLSPAN="4"> 30: [28:30)</TD> <TD COLSPAN="4"> 31: [30:32)</TD> </TR> <TR> <TD COLSPAN="2" BGCOLOR="Purple">32: 0</TD> <TD COLSPAN="2">33: 1</TD> <TD COLSPAN="2">34: 2</TD> <TD COLSPAN="2">35: 3</TD> <TD COLSPAN="2">36: 4</TD> <TD COLSPAN="2" SIDES="LTB" BORDER="5">37: 5</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">38: 6</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">39: 7</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">40: 8</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">41: 9</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">42: 10</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">43: 11</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">44: 12</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">45: 13</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">46: 14</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">47: 15</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">48: 16</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">49: 17</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">50: 18</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">51: 19</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">52: 20</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">53: 21</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">54: 22</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">55: 23</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">56: 24</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">57: 25</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">58: 26</TD> <TD COLSPAN="2" SIDES="B" BORDER="5">59: 27</TD> <TD COLSPAN="2" SIDES="TRB" BORDER="5">60: 28</TD> <TD COLSPAN="2">61: 29</TD> <TD COLSPAN="2">62: 30</TD> <TD COLSPAN="2">63: 31</TD> </TR> </TABLE>> ]; } ``` 長度為 $2$ 的冪的陣列建構而成的線段樹，本身就是一棵完美二元樹，規律性也相當完美，陣列元素會連續地放在 $[n:2n)$，其餘同一層（代表的子陣列長度相同）的節點，也都是連續擺放的；這代表我們並不需要每次都往下遞迴，而是可以直接從底層開始。 :::danger 區間 $[l:r)$ 對應的節點在 $[n+l,n+r)$。 ::: > 這邊假設函式有交換律（Commutative property）； > 如果沒有的話，也稍微進行修改就可以了。 * `build()` * 節點編號從大到小，就可以確保子節點都先初始 * `modify()` * 從樹葉出發，一直往父節點移動 * `query` * 從一堆樹葉出發，如果左右子節點都在區間內，就繼續往上；否則就要加入答案之中 > `<< 1` 等於 `* 2`, `>> 1` 等於 `/ 2` > 模板的設計上跟 `std::priority_queue` 很像。 ```cpp! template<typename value_t, class merge_t> class SGT { int n; vector<value_t> t; // root starts at 1 merge_t merge; // associative function for SGT public: explicit SGT(int _n = 0, const merge_t& _merge = merge_t{}) : n{_n}, t(2 * n), merge{_merge} {} void build(const vector<value_t>& v) { n = v.size(), t.resize(2 * n); for (int p{2 * n - 1}; p >= n; --p) t[p] = v[p - n]; for (int p{n - 1}; p >= 0; --p) t[p] = merge(t[p << 1], t[(p << 1) + 1]); } void modify(int p, const value_t& x) { for (t[p += n] = x; p > 1; p >>= 1) t[p >> 1] = merge(t[p], t[p ^ 1]); } value_t query(int l, int r, value_t init) { // [l:r) for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) init = merge(init, t[l++]); if (r & 1) init = merge(init, t[--r]); } return init; } }; ``` > `query()` 的 `init` 是為了讓程式碼較精簡，也可用 `std::optional` 取代。 > 詢問函式為和時，`init` 給 $0$；詢問函式為最大值時，`init` 給一個極小值， > 或是如果元素都是負值，希望答案為 $0$，也可以把 `init` 給 $0$。可能讀者覺得好像沒有很精簡阿？我們仔細來看看， `build()` 三行，`modify()` 一行，`query` 五行，從遞迴改為迴圈，竟然還只剩下**九行程式碼**！也不用像之前一樣有四個五個的參數。 > 不過它主要適合單點修改區間查詢的操作，快速並容易實作， > 缺點就是沒什麼拓展性，例如要做區間修改就會變得很麻煩。 <hr class="dashed"> 神奇的是，在長度不是 $2$ 的冪時，完全一樣的程式碼還是可以正常運作，基本上節點還是維持著一層一層的架構，沒有用（灰色）的節點就不管它們。 > 改到了也沒關係，因為完全不會用到它們的值。陣列長度 $37$ 的線段樹，查詢區間為 $[5:29)$： ```graphviz digraph { SGT [shape=none, label= <<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="8" CELLPADDING="0"> <TR> <TD COLSPAN="64" BGCOLOR="GhostWhite" BORDER="0"> 1: -</TD> </TR> <TR> <TD COLSPAN="32" BGCOLOR="GhostWhite" BORDER="0"> 2: -</TD> <TD COLSPAN="32" BGCOLOR="Coral" SIDES="LTR" BORDER="5"> 3: [11:27)</TD> </TR> <TR> <TD COLSPAN="16" BGCOLOR="GhostWhite" BORDER="0"> 4: -</TD> <TD COLSPAN="16" BGCOLOR="Gold"> 5: [3:11)</TD> <TD COLSPAN="16" BGCOLOR="Gold" SIDES="L" BORDER="5"> 6: [11:19)</TD> <TD COLSPAN="16" BGCOLOR="Gold" SIDES="R" BORDER="5"> 7: [19:27)</TD> </TR> <TR> <TD COLSPAN="8" BGCOLOR="Gold"> 8: [27:35)</TD> <TD COLSPAN="8" BGCOLOR="GhostWhite" BORDER="0"> 9: -</TD> <TD COLSPAN="8" BGCOLOR="LawnGreen">10: [3:7)</TD> <TD COLSPAN="8" BGCOLOR="LawnGreen" SIDES="LT" BORDER="5">11: [7:11)</TD> <TD COLSPAN="8" BGCOLOR="LawnGreen" BORDER="0">12: [11:15)</TD> <TD COLSPAN="8" BGCOLOR="LawnGreen" BORDER="0">13: [15:19)</TD> <TD COLSPAN="8" BGCOLOR="LawnGreen" BORDER="0">14: [19:23)</TD> <TD COLSPAN="8" BGCOLOR="LawnGreen" SIDES="R" BORDER="5">15: [23:27)</TD> </TR> <TR> <TD COLSPAN="4" BGCOLOR="LawnGreen"> 16: [27:31)</TD> <TD COLSPAN="4" BGCOLOR="LawnGreen"> 17: [31:35)</TD> <TD COLSPAN="4" BGCOLOR="GhostWhite" BORDER="0"> 18: -</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue"> 19: [1:3)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue"> 20: [3:5)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue" SIDES="LT" BORDER="5"> 21: [5:7)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue" BORDER="0"> 22: [7:9)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue" BORDER="0"> 23: [9:11)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue" BORDER="0"> 24: [11:13)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue" BORDER="0"> 25: [13:15)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue" BORDER="0"> 26: [15:17)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue" BORDER="0"> 27: [17:19)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue" BORDER="0"> 28: [19:21)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue" BORDER="0"> 29: [21:23)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue" BORDER="0"> 30: [23:25)</TD> <TD COLSPAN="4" BGCOLOR="DeepSkyBlue" BORDER="0"> 31: [25:27)</TD> </TR> <TR> <TD COLSPAN="2" BGCOLOR="DeepSkyBlue" SIDES="TR" BORDER="5">32: [27:29)</TD> <TD COLSPAN="2" BGCOLOR="DeepSkyBlue">33: [29:31)</TD> <TD COLSPAN="2" BGCOLOR="DeepSkyBlue">34: [31:33)</TD> <TD COLSPAN="2" BGCOLOR="DeepSkyBlue">35: [33:35)</TD> <TD COLSPAN="2" BGCOLOR="DeepSkyBlue">36: [35:37)</TD> <TD COLSPAN="2" BGCOLOR="Violet">37: 0</TD> <TD COLSPAN="2" BGCOLOR="Violet">38: 1</TD> <TD COLSPAN="2" BGCOLOR="Violet">39: 2</TD> <TD COLSPAN="2" BGCOLOR="Violet">40: 3</TD> <TD COLSPAN="2" BGCOLOR="Violet">41: 4</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="LB" BORDER="5">42: 5</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">43: 6</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">44: 7</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">45: 8</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">46: 9</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">47: 10</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">48: 11</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">49: 12</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">50: 13</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">51: 14</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">52: 15</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">53: 16</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">54: 17</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">55: 18</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">56: 19</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">57: 20</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">58: 21</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">59: 22</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">60: 23</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">61: 24</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">62: 25</TD> <TD COLSPAN="2" BGCOLOR="Violet" SIDES="B" BORDER="5">63: 26</TD> </TR> <TR> <TD COLSPAN="1" BGCOLOR="Violet" SIDES="B" BORDER="5">64: 27</TD> <TD COLSPAN="1" BGCOLOR="Violet" SIDES="RB" BORDER="5">65: 28</TD> <TD COLSPAN="1" BGCOLOR="Violet">66: 29</TD> <TD COLSPAN="1" BGCOLOR="Violet">67: 30</TD> <TD COLSPAN="1" BGCOLOR="Violet">68: 31</TD> <TD COLSPAN="1" BGCOLOR="Violet">69: 32</TD> <TD COLSPAN="1" BGCOLOR="Violet">70: 33</TD> <TD COLSPAN="1" BGCOLOR="Violet">71: 34</TD> <TD COLSPAN="1" BGCOLOR="Violet">72: 35</TD> <TD COLSPAN="1" BGCOLOR="Violet">73: 36</TD> </TR> </TABLE>> ]; } ``` > 只看有用的點的話，它也不算一個樹，而是一個深林。詳細證明可以參考 ["Efficient and easy segment trees" proof](https://codeforces.com/blog/entry/89313)。 --- # 線段樹應用（Applications of Segment Tree） ### [逆序數對（Inversions）](https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/A) :::info 給定一個長度為 $n$ 的陣列，元素最大不超過 $n$，對於每一個 $i$，請找出有幾個 $j$，使得 $j\lt i$ 且 $a_j\gt a_i$。 ::: 建立一個 $cnt$ 陣列，$cnt[i]$ 代表數字 $i$ 出現的次數，這樣某個範圍的總和，就等於是這之間的數字個數，而區間查詢我們可以透過線段樹來快速計算。 ```cpp! const int MaxValue{n}; SGT<int, plus<int>> sgt{}; sgt.build(vector<int>(MaxValue + 1, 0)); vector<int> inv(n); for (int i{0}; i < n; ++i) { inv[i] = sgt.query(v[i] + 1, MaxValue + 1, 0); sgt.modify(v[i], sgt.query(v[i], v[i] + 1, 0) + 1); } ``` <hr class="dashed"> ### [最大連續和（Maximum Subarray）](https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/A) :::info 給定一個長度為 $n$ 的陣列，支援下列二種操作： * 將第 $i$ 個元素改為 $x$ * 詢問區間 $[l:r)$ 中的最大連續和 ::: [前面](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-WayOfThinking#%E5%88%86%E6%B2%BB%EF%BC%88Divide-and-Conquer%EF%BC%89)最大連續和時說過，最大連續和等於左邊的最大連續和，右邊的最大連續和，或橫跨二邊的最大連續和。但我們不想要每次都去重新計算橫跨二邊的最大連續和，因此對於每個子區間，我們多紀錄最大前綴和與最大後綴和，左邊子區間最大後綴和加上右邊子區間最大前綴和，即是橫跨二邊的最大連續和。 ```cpp! struct value_t { long long sum, pre, suf, mx; value_t()=default; value_t(long long x) : sum{x}, pre{x}, suf{x}, mx{x} {} }; struct merge_t { value_t operator()(const value_t& x, const value_t& y) { value_t res{}; res.sum = x.sum + y.sum; res.pre = max(x.pre, x.sum + y.pre); res.suf = max(x.suf + y.sum, y.suf); res.mx = max(max(x.mx, y.mx), x.suf + y.pre); return res; } }; ``` > :bulb:這邊寫了一個 [Converting constructor](https://en.cppreference.com/w/cpp/language/converting_constructor)，讓它可以進行隱式轉換（Implicit conversions）。接著就可以直接套用線段樹的模板了。此合併函式不具有交換律，須注意運算元的前後順序，所以這題使用基本線段樹，需要考慮的問題會少一點，不過這邊示範如何使用極簡線段樹來實現。 > `init` 給 $0$，在這邊可視為在詢問區間 $[l:r)$ 前後各加上一個 $0$， > 如果 $[l:r)$ 的最大連續和為負值，答案剛好變為 $0$，也就是空區間的答案， > 否則不影響結果（`mx` 的部分）； > `init` 如果給一個很小的值，則完全不影響結果。 :::spoiler 完整程式碼 ```cpp! #include <iostream> #include <vector> using namespace std; template<typename value_t, class merge_t> class SGT { int n; vector<value_t> t; // root starts at 1 merge_t merge; // associative function for SGT public: explicit SGT(int _n = 0, const merge_t& _merge = merge_t{}) : n{_n}, t(2 * n), merge{_merge} {} void modify(int p, const value_t& x) { for (t[p += n] = x; p > 1; p >>= 1) if (p & 1) t[p >> 1] = merge(t[p - 1], t[p]); else t[p >> 1] = merge(t[p], t[p + 1]); } value_t query(int l, int r, value_t init) { // [l:r) value_t L{init}, R{init}; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) L = merge(L, t[l++]); if (r & 1) R = merge(t[--r], R); } return merge(L, R); } }; void solve() { int n, m; cin >> n >> m; struct value_t { long long sum, pre, suf, mx; value_t()=default; value_t(long long x) : sum{x}, pre{x}, suf{x}, mx{x} {} }; struct merge_t { value_t operator()(const value_t& x, const value_t& y) { value_t res{}; res.sum = x.sum + y.sum; res.pre = max(x.pre, x.sum + y.pre); res.suf = max(x.suf + y.sum, y.suf); res.mx = max(max(x.mx, y.mx), x.suf + y.pre); return res; } }; SGT<value_t, merge_t> sgt{n}; for (int i{0}; i < n; ++i) { long long x; cin >> x; sgt.modify(i, x); } cout << sgt.query(0, n, 0).mx << '\n'; while (m--) { int i; long long x; cin >> i >> x; sgt.modify(i, x); cout << sgt.query(0, n, 0).mx << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t{1}; // cin >> t; while (t--) solve(); return 0; } ``` ::: <hr class="dashed"> ### [第 $k$ 個 $1$（K-th one）](https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/B) :::info 給定一個長度為 $n$ 的陣列，元素為 $0$ 或 $1$，支援下列二種操作： * 將第 $i$ 個元素反轉（$0\to 1,1\to 0$） * 詢問第 $k$ 個 $1$ 的位置 ::: 「第 $k$ 個 $1$ 的位置」這個問題好像不知道如何下手，考慮一個更一般化的問題，「第一個前綴和大於等於 $x$ 的位置」。先建立一棵合併函式為和的線段樹，我們就可以在線段樹上進行二分搜，如果左子陣列的和大於等於 $ps$，代表答案在左邊，否則答案則在右邊。 > 記得先確認整個子陣列的和有大於 $ps$，之後就可以保證答案一定在 $[tl:tr)$ 之間。 ```cpp! int ps_lower_bound(int ps) { // prefix sum lower bound if (t[1] < ps) return n; int tv{1}, tl{0}, tr{n}; while (tr - tl > 1) { int tm{(tl + tr) / 2}; if (t[left(tv)] >= ps) tv = left(tv), tr = tm; else ps -= t[left(tv)], tv = right(tv, tl, tm), tl = tm; } return tl; } ``` :::spoiler 完整程式碼 ```cpp! class SGT { int n; vector<int> t; int left(int tv) { return tv + 1; } int right(int tv, int tl, int tm) { return tv + 2 * (tm - tl); } void build(const vector<int>& v, int tv, int tl, int tr) { if (tr - tl == 1) t[tv] = v[tl]; else { int tm{(tl + tr) / 2}; build(v, left(tv), tl, tm); build(v, right(tv, tl, tm), tm, tr); t[tv] = t[left(tv)] + t[right(tv, tl, tm)]; } } void flip(int p, int tv, int tl, int tr) { if (tr - tl == 1) t[tv] = (t[tv] == 0 ? 1 : 0); else { int tm{(tl + tr) / 2}; if (p < tm) flip(p, left(tv), tl, tm); else flip(p, right(tv, tl, tm), tm, tr); t[tv] = t[left(tv)] + t[right(tv, tl, tm)]; } } public: SGT(const vector<int>& v) : n{v.size()}, t(2 * n) { build(v, 1, 0, n); } void flip(int p) { flip(p, 1, 0, n); }; int ps_lower_bound(int ps) { // prefix sum lower bound if (t[1] < ps) return n; int tv{1}, tl{0}, tr{n}; while (tr - tl > 1) { int tm{(tl + tr) / 2}; if (t[left(tv)] >= ps) tv = left(tv), tr = tm; else ps -= t[left(tv)], tv = right(tv, tl, tm), tl = tm; } return tl; } }; ``` ::: > 透過適當的合併函式，我們一樣可以在線段樹上進行二分搜，找到不同問題的答案， > 例如合併函式為最大值，我們可以找到「第一個大於 $x$ 的元素位置」。 --- # 稀疏表（Sparse Table） > 前面說到不能根據 $[l:r)$ 對半切分，因為有太多不同的子區間的話， > 想要事先計算就會變得不切實際，空間時間複雜度都會很高。考慮區間最小值查詢（RMQ, Range Minimum Query），會發現子問題的區間可以是重疊的，畢竟一個值被多考慮幾次，也不會影響最小值是什麼。所以我們可以讓子區間的長度有一定特性，這樣不同查詢有可能出現的子區間數量就可以被限制住。 ```graphviz digraph { SGT [shape=none, label= <<TABLE BORDER="1" CELLBORDER="0" CELLSPACING="2" CELLPADDING="4"> <TR> <TD COLSPAN="8" BGCOLOR="LightCyan" HEIGHT="15"></TD> <TD COLSPAN="5"></TD> </TR> <TR> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray">l</TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray">l+1</TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray">l+2</TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray"></TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray"></TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray"></TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray"></TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray"></TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray"></TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray"></TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray"></TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray"></TD> <TD COLSPAN="1" BORDER="1" WIDTH="30" BGCOLOR="LightGray">r-1</TD> </TR> <TR> <TD COLSPAN="5"></TD> <TD COLSPAN="8" BGCOLOR="Pink" HEIGHT="15"></TD> </TR> </TABLE>> ]; } ``` 如果子區間的長度都是 $2$ 的冪，將區間分成 $[l:l+2^{\lfloor\log_2(r-l)\rfloor})$ 與 $[r-2^{\lfloor\log_2(r-l)\rfloor}:r)$，足以涵蓋整個區間，所以事先計算每個點開始，長度為 $2$ 的冪的區間最小值。 <hr class="dashed"> ## 實作（Implementation）令 $st[i][j]$ 等於 $[i,i+2^j)$ 的最小值， $[i,i+2^j)$ 可以分半，也就等於 $[i,i+2^{j-1})$ 與 $[i+2^{j-1},i+2^j)$ 二個區間的最小值。 :::success $st[i][j]=\min(st[i][j-1],st[i+2^{j-1}][j-1])$ ::: 令 $log2[i]$ 代表 $\lfloor\log_2i\rfloor$。 > 若 $k$ 為偶數，$k=2n$， > > $2^{log2[n]}\le n\lt 2^{log2[n]+1}$ > $\to 2^{log2[n]+1}\le 2n\lt 2^{log2[n]+2}$ > > 則 $log2[k]=log2[k/2]+1$。 > > 若 $k$ 為奇數，$k=2n+1$， > > $2^{log2[n]}\le n\lt 2^{log2[n]+1}$ > $\to 2^{log2[n]}\le n\le 2^{log2[n]+1}-1$ > $\to 2^{log2[n]+1}\le 2n\le 2^{log2[n]+2}-2$ > $\to 2^{log2[n]+1}\le 2n+1\lt 2^{log2[n]+2}$ > > 則 $log2[k]=log2[k/2]+1$。 :::success $log2[i]=log2[i/2]+1$ ::: ```cpp! vector<int> log2(n + 1); log2[1] = 0; for (int i{2}; i <= n; ++i) log2[i] = log2[i / 2] + 1; vector<vector<int>> st(n, vector<int>(log2[n] + 1)); for (int i{n - 1}; i >= 0; --i) { st[i][0] = v[i]; for (int j{1}; i + (1 << j) <= n; ++j) st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } ``` 建表複雜度為 $O(n\log n)$。 ```cpp! int j{log2[r - l]}; min(st[l][j], st[r - (1 << j)][j]); ``` 查詢複雜度為 $O(1)$。稀疏表的威力就在於 $O(1)$ 的最小值查詢，只可惜它不能支援快速的修改。 :::spoiler 完整程式碼 ```cpp! // sparse table template<typename value_t, class merge_t> class ST { int n; vector<int> log2; vector<vector<value_t>> t; merge_t merge; // associative & idempotent function for ST public: explicit ST(const vector<value_t>& v, const merge_t& _merge = merge_t{}) : n{v.size()}, log2(n + 1), merge{_merge} { log2[1] = 0; for (int i{2}; i <= n; ++i) log2[i] = log2[i / 2] + 1; t.assign(n, vector<value_t>(log2[n] + 1)); for (int i{n - 1}; i >= 0; --i) { t[i][0] = v[i]; for (int j{1}; i + (1 << j) <= n; ++j) t[i][j] = merge(t[i][j - 1], t[i + (1 << (j - 1))][j - 1]); } } value_t query(int l, int r) { // [l:r) int j{log2[r - l]}; return merge(t[l][j], t[r - (1 << j)][j]); } }; ``` ::: --- # References * Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed (2007). "Fundamentals of Data Structures in C, 2/e". * CP-Algorithms - [Segment Tree](https://cp-algorithms.com/data_structures/segment_tree.html) * [Codeforces ITMO Academy: pilot course » Segment Tree](https://codeforces.com/edu/course/2/lesson/4) * [Efficient and easy segment trees](https://codeforces.com/blog/entry/18051) * ["Efficient and easy segment trees" proof](https://codeforces.com/blog/entry/89313) * CP-Algorithms - [Sparse Table](https://cp-algorithms.com/data_structures/sparse-table.html) * Algorithmica - [Algorithms for Modern Hardware 11.3 Segment trees](https://en.algorithmica.org/hpc/data-structures/segment-trees/) --- # 練習題 | Problem | Tags | |:-:|:- | | [Xenia and Bit Operations](https://codeforces.com/contest/339/problem/D) | `segment tree` | | [Pashmak and Parmida's problem](https://codeforces.com/contest/459/problem/D) | `segment tree` | | [Petya and Array](https://codeforces.com/contest/1042/problem/D) | `segment tree` | | [Flip](https://codeforces.com/gym/103373/problem/F) | `segment tree`, `range modification` | | [區間 MAX](https://zerojudge.tw/ShowProblem?problemid=d539) | `sparse table` | [^CPAlgo]: CP-Algorithms - [Segment Tree, Memory efficient implementation](https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-6) [^EESGT]: [Efficient and easy segment trees](https://codeforces.com/blog/entry/18051) <style> hr.thin { height: 0.5px; } hr.dotted { border-top: dotted; height: .0em; color: #777777; background-color: #ffffff; } hr.dashed { border-top: dashed; height: .0em; color: #777777; background-color: #ffffff; } /* Gradient transparent - color - transparent */ hr.gradient { border: 0; height: 1px; background-image: linear-gradient(to right, rgba(0, 0, 0, 0), rgba(0, 0, 0, 0.75), rgba(0, 0, 0, 0)); } /* Flaired edges, by Tomas Theunissen */ hr.flaired { overflow: visible; height: 30px; border-style: solid; border-color: black; border-width: 1px 0 0 0; border-radius: 20px; background-color: #ffffff; } hr.flaired:before { /* Not really supposed to work, but does */ display: block; content: ""; height: 30px; margin-top: -31px; border-style: solid; border-color: black; border-width: 0 0 1px 0; border-radius: 20px; } </style>

Read more

C++S's CODEBOOK

2021 Week12 - Graph (BCC, SCC, LCA)

2021 Week17 - Matching

2021 Week17 - Cover & Independent set