# 進階資料結構與莫隊算法—線段樹 ###### tags: `108 師大附中校隊培訓` ###### wiwiho --- ## 什麼是線段樹 ---- 把塊分割 ---- 整個序列列是一大塊 這一塊可以二等分成兩小塊 每一小塊又可以再二等分 這樣一直二等分下去 到最後會分到每一塊都剩下一個元素 ---- 這樣可以畫成一棵二元樹 ---- 根節點表示整個序列 它的左子節點表示它的左半部 右子節點表示它的右半部 ---- 每個節點的左子節點 都表示該節點所表示範圍的左半部 右子節點表示右半部 葉節點則表示只有一個元素的區間 ---- 每一個節點都表示一個區間 而每個節點表示的區間都 完整包含了其子節點所表示的區間 ----  ---- ## 索引要從 $0$ 或從 $1$ 開始？ 實作上幾乎沒差，看習慣 ---- ## 區間表示要左閉右閉（$[l,r]$）或左閉右開($[l,r)$)？ 實作上差不多，也看習慣 ---- 在每一個節點上 儲存在那個區間中我們想要的答案 父節點的答案可以從兩個子節點來得到 --- ## 儲存 ---- 二元樹有兩種存法 1. 指標 2. 陣列 ---- 不動態開點的話 線段樹通常都用陣列 ---- 線段樹的每個節點的兩子樹會是平衡的 因此除了它最深的那一層 其他層都會是滿的 ---- - 根節點的編號是 $0$ - $i$ 的左子節點編號會是 $2i+1$ - 右子節點編號是 $2i+2$ - 根節點編號是 $1$ - 節點 $i$ 的左子節點編號是 $2i$ - 右子節點是 $2i+1$ 用哪種？看習慣就好 ---- ## 陣列該開多大？ ---- 看節點編號最多會用到多少 ---- 有 $2^i$（$i$ 是非負整數）個葉節點的滿二元樹 - 非葉節點會有 $2^i-1$ 個 - 總節點數是 $2^{i+1}-1$ ---- 線段樹的葉節點數和序列長度是一樣的 如果這個數字是 $n$，那麼葉節點會有 $n$ 個 ---- 如果把最後一層填滿 會有 $2^{\lceil\log_2n\rceil}$ 個葉節點 整棵樹會有 $2^{\lceil\log_2n\rceil+1}-1$ 個節點 ---- 如果 $n=2^i+a$，$0<a<2^i$ $2^{\lceil\log_2n\rceil}=2^{i+1}$ $2^{\lceil\log_2n\rceil+1}-1=2^{i+2}-1<2^{i+2}$ ---- $n \times 4$ 一定會大於總節點數 陣列大小通常都會取 $n \times 4$ --- ## 建構 ---- 一直遞迴去把區間二等分填數字就好 ---- ``` array segment_tree; //用來存線段樹的那個陣列，用普通陣列或vector都可 array a; //序列 int n; //a的大小 //v的區間是[L,R] void build(int L, int R, vertex v){ if(L == R){ a[v] = 用a[i]得出答案; return; } int M = (L + R) / 2; //把區間二等分 build(L, M, v的左子節點); build(M + 1, R, v的右子節點); } ``` ---- 複雜度和節點數一樣 是 $O(n)$ --- ## 單點修改 ---- 先找到表示那個點的葉節點 並且更新它和它的所有祖先 ---- ``` //節點 v 的區間範圍是[L,R]，要修改的地方是pos，新值是value void modify(type value, int pos, int L, int R, vertex v){ if(L == R){ //找到了葉節點 修改 v; return; } int M = (L + R) / 2; //[L,R]區間的中點 //將這個區間二等分，左半的範圍是[L,R]，右半是[M+1,R] if(pos >= L && pos <= M) //pos在左半部 modify(value, pos, L, M, v的左子節點); else //pos在右半部 modify(value, pos, M+1, R, v的右子節點); 根據v的左子節點和右子節點的答案更改v的答案; } ``` ---- 線段樹的深度最深就是 $\lceil\log_2n\rceil$ 因此遞迴次數為 $O(\log n)$ 時間複雜度 $O(\log n)$ --- ## 區間查詢 ---- 遇到有一個節點的範圍 被完整包含在查詢範圍內 可以直接取這個節點記錄的答案 而不用往下找 ---- ``` //查詢範圍是[l,r]，節點v的區間範圍是[L,R] type query(int l, int r, int L, int R, vertex v){ if(l == L && r == R) //[L,R]完整被查詢區間所包含 return ans of v; int M = (L + R) / 2; if(r <= M) //如果查詢區間都在左半部，就只查左半部 return query(l, r, L, M, v的左子節點); else if(l > M) //如果查詢區間都在右半部，就只查右半部 return query(l, r, M + 1, R, v的右子節點); else{ //如果查詢區間跨越兩半部，那就也把查詢區間切半 //這樣可以確保遞迴後[l,r]一定在[L,R]之內 return 用query(l, M, L, M, v的左子節點) 和query(M + 1, r, M + 1, R, v的右子節點) 得出區間[l,r]的答案; } } ``` ----  ---- 被遞迴到的點一開始會是一條線 直到表示兩個端點的葉節點的 LCA 然後開始分叉成兩條畫到兩個端點的線 還有左分叉線上的每一個節點的右子節點 與右分叉線上的每一個節點的左子節點 ----  ---- 這數量最多就差不多深度的四倍而已 複雜度也是 $O(\log n)$ --- ## 懶人標記 ---- 區間修改？ 用懶人標記 ---- 在節點上記錄對答案的變動 ---- 查詢時要往下遞迴 必須要把經過節點的懶人標記往下推 這樣在查子節點的時候答案才是對的 ---- ``` //新值是value，修改區間是[l,r]，節點v的範圍是[L,R] void modify(type value, int l, int r, int L, int R, vertex v){ if(l == L && r == R){ 打懶標在v上; return; } int M = (L + R) / 2; if(r <= M) modify(value, l, r, L, M, v的左子節點); else if(l > M) modify(value, l, r, M + 1, R, v的右子節點); else{ modify(value, l, M, L, M, v的左子節點); modify(value, M + 1, r, M + 1, R, v的右子節點); } 用兩個子節點的答案更新v的答案; } ``` ---- ``` //查詢範圍是[l,r]，節點v的區間範圍是[L,R] type query(int l, int r, int L, int R, vertex v){ if(l == L && r == R) return ans of v; 把節點v的懶標下推; //<---- int M = (L + R) / 2; if(r <= M) return query(l, r, L, M, v的左子節點); else if(l > M) return query(l, r, M + 1, R, v的右子節點); else{ return 用query(l, M, L, M, v的左子節點) 和query(M + 1, r, M + 1, R, v的右子節點) 得出區間[l,r]的答案; } } ``` ---- 複雜度和區間查詢一樣 $O(\log n)$ --- ## 動態開點 ---- 在動態開點的時候 用指標來存線段樹 ---- 區間範圍非常大 而且題目讓你也很難離散化 ---- 陣列開線段樹 記憶體一定不夠 但是根本只會用到其中幾個節點而已 ---- 可以用動態開點 只要開你需要的節點就好 --- ## 高維線段樹 ---- 線段樹可以有很多維度 在每個 $D$ 維線段樹的節點放一棵 $D-1$ 維的線段樹 ---- 在每一個節點都要往下查低一維的線段樹 所以複雜度是 $\log_2^Dn$