原創作時間：\(\texttt{2022-05-03 10:33:43}\)
閱讀前
By Xie Zheyuan.
這里有一份 《線段樹學習筆記》 AC代碼索引 里面有AC代碼，
若有謬誤，敬請在評論區指出，
簡介
線段樹是一個維護區間資訊的資料結構，只要資訊維護滿足結合律，就可以使用線段樹，
基本思路
例題
下面的思路介紹以 P3372 【模板】線段樹 1 為例，
如題，已知一個數列，你需要進行下面兩種操作：
- 將某區間每一個數加上 \(k\)，
- 求出某區間每一個數的和，
總體思路
線段樹是將一個數列映射到一棵完全二叉樹，其中每一個節點維護一個區間，
根節點維護 \([1,n]\)，然后左子節點維護 \([1,\lfloor n \div 2 \rfloor]\)，右子節點維護 \([\lfloor n \div 2 \rfloor+1,n]\)，
葉子節點維護的區間左右端點相等，
我們可以用二進制表示法表示線段樹，即用 \(i\) 表示父節點，\(2i\) 表示左子節點， \(2i+1\) 表示右子節點，根節點為 \(1\)，這樣就可以用一個組表示一棵線段樹了，
來源：Senior Data Structure · 淺談線段樹（Segment Tree） - 笨蛋花的小窩qwq - 洛谷博客
所以，我們可以定義以下宏：
#define ls (i<<1) // 左子節點
#define rs (i<<1|1) // 右子節點
#define mid ((l+r)>>1) // 當前區間中部
資料上推（pushup）
原題維護的是區間和，因此我們需要將左右子樹的值相加，即為父節點的值，代碼如下：
void pushup(int i){
tree[i]=tree[ls]+tree[rs];
}
時間復雜度 \(O(1)\)，
建樹（build）
建樹其實就是一個樹上DFS程序，
首先，從根節點開始，向下遍歷，當遇到葉子節點時，我們把它的值賦為原陣列的值，
Q:那么，如何判斷葉子節點，如何求出在原陣列的位置呢？
A:可以在遍歷時記錄 \([l,r]\)，表示當前遍歷的區間，
所以遍歷時我們需要記錄三個值，\(i\)（當前遍歷在二叉樹陣列的位置），\(l\)，\(r\)，
最后，遍歷左右子樹完成，更新當前節點，也就是 pushup，
代碼如下：
void build(int i,int l,int r){
if(l==r){
tree[i]=a[i];
return ;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
時間復雜度 \(O(n)\)，
沒有標記的單點修改
單點修改很簡單，直接在樹上二分找出節點，修改后逐級 pushup 即可，
由于本題沒有出現單點修改，于是不放代碼了，
時間復雜度 \(O(\log n)\)，
區間修改-標記下傳（pushdown）
區間修改肯定不是執行 \(r-l+1\) 次單點修改，這樣子時間復雜度 \(O(n\log n)\)，比暴力還慢
為了解決該問題，我們引入一個概念，懶標記（lazy tag，一般簡稱tag），
我們可以在要修改的區間內打一個標記，然后訪問的時候再下傳就好了，
可以看出，這個操作正好與 pushup 相反，所以稱之為 pushdown，
下傳代碼如下：
void pushdown(int i,int l,int r){
if(tag[i]){ // 如果有標記
tag[ls]+=tag[i]; // 左節點更新標記
tag[rs]+=tag[i]; // 右節點更新標記
tree[ls]+=(mid-l+1)*tag[i]; // 左節點更新值
tree[rs]+=(r-mid)*tag[i]; // 右節點更新值
tag[i]=0; // 清除當前節點標記
}
}
時間復雜度 \(O(1)\)，
區間修改（update）
有了之前的標記下傳，我們可以在樹上二分 最靠近根節點的覆寫了所有修改區間的幾個區間，然后打上標記，最后上傳，
代碼如下：
void update(int i,int l,int r,int x,int y,int k){
if(l>=x&&r<=y){ // 被包含
tree[i]+=(r-l+1)*k; // 修改本身的值
tag[i]+=k; // 打標記
return ;
}
pushdown(i,l,r); // 標記下傳
if(mid>=x) update(ls,l,mid,x,y,k);
if(mid<y) update(rs,mid+1,r,x,y,k); // 二分
pushup(i); // 上傳
}
時間復雜度 \(O(\log n)\)，
區間查詢（query）
這個比較簡單，二磁區間，然后統計值即可，記得要下傳標記，
代碼如下：
int query(int i,int l,int r,int x,int y){
if(l>=x&&r<=y){ // 被包含
return tree[i];
}
pushdown(i,l,r);// 標記下傳
int ret=0;
if(mid>=x) ret+=query(ls,l,mid,x,y);
if(mid<y) ret+=query(rs,mid+1,r,x,y);// 二分
return ret;
}
時間復雜度 \(O(\log n)\)，
有標記單點修改單點查詢
這些都是區間操作的特例，所以沒什么好說的，
時間復雜度 \(O(\log n)\)，
總結
pushdown的規律
pushdown 在除 build 外所有需要 向下二分（遞回） 的地方 之前 必須要呼叫，
pushup的規律
pushup 除 query 外所有需要 向下二分（遞回） 的地方 之后 必須要呼叫，
時間復雜度
| 操作 | 時間復雜度 |
|---|---|
| 資料上傳 | \(O(1)\) |
| 建樹 | \(O(n)\) |
| 標記下傳 | \(O(1)\) |
| 單點/區間修改 | \(O(\log n)\) |
| 單點/區間查詢 | \(O(\log n)\) |
關于陣列大小
二叉樹陣列、懶標記陣列一律遵循 4倍空間 原則，即大小為 \(4n\)，（建議留一些富余）
基礎線段樹應用
RMQ類
P1531 I Hate It
你需要實作一個資料結構 \(A[]\)，長度為 \(n\),有 \(m\) 個操作，支持:
-
Q a b，求 \(\min\limits_{i=a}^{b}{A_i}\)， -
C a b，將 \(A[a]\) 賦為 \(b\)，
\(0 \lt n \le 2 \times 10 ^5,0 \lt m \lt 5000\)
這是一道（帶修）RMQ問題，可以用線段樹維護區間 \(\min\)，然后實作單點修改區間查詢即可，
時間復雜度為 \(O(n+m\log n)\)，
P1198 [JSOI2008]最大數 | BZOJ1012 [JSOI2008]最大數maxnumber
你需要實作一個資料結構 \(A[]\),初始為空，有 \(M\) 個操作，
Q L，查詢末尾 \(L(L \gt 0)\) 個數中最大的數，A n，將 \(n+t \pmod{B}\) 添加到 \(A[]\) 末尾，其中 \(t\) 是最后一次Q操作的值（初始為 \(0\)），\(B\) 是模數，
\(1 \leq M \leq 2 \times 10^5\)，\(1 \leq D \leq 2 \times 10^9\)
這道題仍然是一道（帶修）RMQ，只是變成了維護區間 \(\max\)，
時間復雜度 \(O(M\log M)\)，
P2880 [USACO07JAN] Balanced Lineup G
你需要實作一個資料結構 \(h[]\)，長度為 \(n\) ，有 \(q\) 個詢問，每個詢問給出\(A\) 與 \(B\)，求 \(\max\limits_{i=A}^{B}{h[i]} - \min\limits_{i=A}^{B}{h[i]}\)，
\(1 \le N \le 50000,1 \le Q \le 180000\)
這道題其實正解是ST表，但也不妨用線段樹來維護，
這道題需要維護多個量，我們可以建兩棵線段樹，同時維護，
時間復雜度 \(O(n+q\log n)\)，
P4392 [BOI2007]Sound 靜音問題
數字錄音中，聲音是用表示空氣壓力的數字序列描述的，序列中的每個值稱為一個采樣，每個采樣之間間隔一定的時間，
很多聲音處理任務都需要將錄到的聲音分成由靜音隔開的幾段非靜音段，為了避免分成過多或者過少的非靜音段，靜音通常是這樣定義的：m個采樣的序列，該序列中采樣的最大值和最小值之差不超過一個特定的閾值c，
請你寫一個程式，檢測n個采樣中的靜音，
列出了所有靜音的起始位置i（i滿足max(a[i, . . . , i+m?1]) ? min(a[i, . . . , i+m?1]) <= c），每行表示一段靜音的起始位置，按照出現的先后順序輸出，如果沒有靜音則輸出NONE，
這道題也是線段樹，可以用暴力建立區間來滑動求解，
時間復雜度 \(O(n \log n)\)，
（原創題）Game 1：人道寄奴曾住
你需要維護一個長為 \(n\) 的序列 \(A\)，支持以下操作：
-
1 l r，將 \(A_l\) 賦值為 \(r\)， -
2 l r，求區間 \([l,r]\) 的歷史最大值，
\(1 \lt n,l,r,A_i \lt 2 \times 10 ^ {5},1 \lt m \lt 5000\)，
時間限制 \(30\text{ms}\)，記憶體限制 \(10\text{MB}\)，
本題不需要可持久化，只需要更改時取 \(\max\) 即可，
時間復雜度 \(O(n+m\log n)\)，
多標記多值
P1253 [yLOI2018] 扶蘇的問題
給定一個長度為 \(n\) 的序列 \(a\)，有 \(q\) 個操作，要求支持如下三個操作：
- 給定區間 \([l, r]\)，將區間內每個數都修改為 \(x\)，
- 給定區間 \([l, r]\)，將區間內每個數都加上 \(x\)，
- 給定區間 \([l, r]\)，求區間內的最大值，
對于 \(100\%\) 的資料，\(1 \leq n, q \leq 10^6\)，\(1 \leq l, r \leq n\)，\(op \in \{1, 2, 3\}\)，\(|a_i|, |x| \leq 10^9\)，
這道題維護了多標記，要注意標記下傳順序，
時間復雜度為 \(O(n + q\log n)\)，
P2023 [AHOI2009] 維護序列 | LibreOJ#10129. 「一本通 4.3 練習 3」維護序列
有一個長為 \(n\) 的數列 \(\{a_n\}\)，有如下三種操作形式：
- 格式
1 t g c，表示把所有滿足 \(t\le i\le g\) 的 \(a_i\) 改為 \(a_i\times c\) ; - 格式
2 t g c表示把所有滿足 \(t\le i\le g\) 的 \(a_i\) 改為 \(a_i+c\) ; - 格式
3 t g詢問所有滿足 \(t\le i\le g\) 的 \(a_i\) 的和，由于答案可能很大，你只需輸出這個數模 \(p\) 的值，
這道題也是多標記，也要注意下傳順序，
時間復雜度為 \(O(n+m\log n)\)，
奇怪維護類
CodeForces718C Sasha and Array
定義 \(F_i\) 為 斐波那契數列的第 \(i\) 項的數，你需要實作一個資料結構 \(a[]\)，支持：
1 l r x：將 \([l,r]\) 的數加上 \(x\)，
2 l r：求 \(\sum\limits_{i=l}^{r}{F_{a[i]}}\)，
\(1 \le n,m \le 10^{5},1 \le a[i] \le 10^{9}\)
線段樹維護矩陣，
\[([1\ 1] \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{i-1})_{1,2} = F_i \]時間復雜度 \(O(n\log^2 n)\)，
P2572 [SCOI2010] 序列操作
埋坑，下回補，
P1438 無聊的數列
維護一個數列 \(a_i\)，長度為 \(n\)，運算元為 \(m\)，支持兩種操作：
-
1 l r K D：給出一個長度等于 \(r-l+1\) 的等引數列，首項為 \(K\)，公差為 \(D\)，并將它對應加到 \([l,r]\) 范圍中的每一個數上，即：令 \(a_l=a_l+K,a_{l+1}=a_{l+1}+K+D\ldots a_r=a_r+K+(r-l) \times D\)， -
2 p：詢問序列的第 \(p\) 個數的值 \(a_p\)，
\(0\le n,m \le 10^5,-200\le a_i,K,D\le 200, 1 \leq l \leq r \leq n, 1 \leq p \leq n\)，
本題可以用線段樹+差分解決，
首先，用線段樹維護原序列 \(a\) 的差分陣列 \(A\)，然后執行：
\[A_l = A_l + s,A_{r+1} = A_{r+1} - e,A_{[l+1:r]}=A_{[l+1:r]}+d \]然后直接單點查詢 \(p\) 即是答案，
時間復雜度 \(O(n+m\log n)\)
維護技巧類
P4145 上帝造題的七分鐘 2 / 花神游歷各國 | LibreOJ#6281. 數列分塊入門 5
你需要實作一個資料結構 \(a[]\)，長度為 \(n\)，有 \(m\) 個操作，支持一下操作：
0 l r: 將 \([l,r]\) 的數 \(a[i]=\lfloor \sqrt{a[i]} \rfloor\)1 l r求 \(\sum\limits_{i=l}^{r}{a[i]}\)
對于 \(100\%\) 的資料，\(1\le n,m\le 5 \times 10^5\)，\(1\le l,r\le n\)，數列中的數大于 \(0\)，且不超過 \(10^{12}\)，
線段樹好題，
本題不能打Lazy tag，只能暴力修改，注意要剪枝，
T218729 mod板 線段樹
一個長度為 \(n\) 的序列，支持以下操作：
-
1 x y求 \(\sum\limits_{i=x}^y a_i\) -
2 x y將 \([x,y]\) 的數開根號并向下取整， -
3 x y k將 \([x,y]\) 中所有數模 \(k\)， -
4 x k將第 \(x\) 個數變為 \(k\)，
\(n \le 10^5, q\le10^5,a_i \le 10^9\)
這道題同樣是上面的道理，另外， \(\bmod\) 操作也要特殊處理，
權值線段樹
簡介
權值線段樹和線段樹略有不同，其實就是在遞回是++，
維護的是出現的次數，
可以用來維護全域第 \(k\) 大/小 的問題，也可以實作逆序對，
全域第k小(P1801 黑匣子)
先離散化，
然后就建權值線段樹，當然，query 要改一下，
如果左節點大于等于 \(k\)，那么左子樹，否則右子樹，
注意，右子樹的 \(k\) 變為 \(k-t[ls]\).
感謝 @five20，
可持久化(主席樹)
可持久化陣列
例題(P3919 【模板】可持久化線段樹 1（可持久化陣列）)
你需要維護這樣的一個長度為 $ N $ 的陣列，支持如下幾種操作
-
在某個歷史版本上修改某一個位置上的值
-
訪問某個歷史版本上的某一位置的值
對于100%的資料：$ 1 \leq N, M \leq {10}^6, 1 \leq {loc}_i \leq N, 0 \leq v_i < i, -{10}^9 \leq a_i, {value}_i \leq {10}^9$
基本思想
主席樹是對線段樹進行擴充，它可以實作可持久化的資料結構，
一般來說，有一棵支持單點修改的線段樹，那么可以加上一些子樹來保存歷史資訊，
就比如說這幅圖：
圖片來源：P3919 【模板】可持久化陣列 -初步探究主席樹 - hyfhaha 的博客
其實，修改的歷史也是一棵樹，可以把它的根節點存在另外一棵類似線段樹的樹里，
然后就沒什么好說的了，代碼在索引里，有注釋，
關于陣列大小
主席樹陣列遵循 32倍空間原則，(本題資料25倍即可）
關于時間復雜度
主席樹時間復雜度與一般的線段樹大致相同，
可持久化權值線段樹
概述
可持久化權值線段樹一般應用在求靜態區間第 \(k\) 大/小 問題，
靜態區間第k小(P3834 【模板】可持久化線段樹 2)
有 \(n\) 個數，\(m\)次詢問某段區間 \([l,r]\) 中第 \(k\) 小的數，
\(1 \le n,m \le 2 \times 10^{5}, |a_i| \le 10^{9},1 \le l,r \le n,1 \le k \le r-l+1\)
這道題是黑匣子的升級版，可以使用版本的差分思想，注意，這道題是權值線段樹，不要寫錯了，
代碼在索引里，
SP3946 MKTHNUM - K-th Number
幾乎是原題，只是資料變小了(降到了 \(1 \le n \le 100000, 1 \le m \le5000\))，
P3567 [POI2014]KUR-Couriers | LibreOJ#2432. 「POI2014」代理商 Couriers
給定一個長度為 \(n\) 的正整數序列 \(a\)，共有 \(m\) 組詢問，每次詢問一個區間 \([l,r]\) ，是否存在一個數在 \([l,r]\) 中出現的次數嚴格大于一半，如果存在，輸出這個數，否則輸出 \(0\)，
\(1 \leq n,m \leq 5 \times 10^5\)，\(1 \leq a_i \leq n\)，
眾所周知這道題全部輸出 \(0\) 有 \(30\) 分
挖坑，等一下埋，
線段樹合并
思想
線段樹合并實際上就是建立一棵線段樹，維護原來兩個資訊的資訊并，
圖片來源：線段樹合并：從入門到放棄 - Styx 的博客 - 洛谷博客
我覺得思想很簡單，直接暴力合并即可，
代碼如下：
void merge(int &a,int &b){
if(!a){
a=b;
}
else if(!b){}
else{
t[a].v+=t[a].v;
}
merge(t[a].l,t[b].l);
merge(t[a].r,t[b].r);
}
這里運用了動態開點線段樹的思想，其實就是不使用傳統的二進制二叉樹，而是定義一個結構體保存左節點（ l），和右節點（ r ），可以有效地減少記憶體 （雖然我不知道為什么）
P3224 [HNOI2012]永無鄉| BZOJ2733 [HNOI2012]永無鄉
永無鄉包含 \(n\) 座島，編號從 \(1\) 到 \(n\) ，每座島都有自己的獨一無二的重要度，按照重要度可以將這 \(n\) 座島排名，名次用 \(1\) 到 \(n\) 來表示，某些島之間由巨大的橋連接，通過橋可以從一個島到達另一個島，如果從島 \(a\) 出發經過若干座（含 \(0\) 座）橋可以 到達島 \(b\) ，則稱島 \(a\) 和島 \(b\) 是連通的，
現在有兩種操作：(運算元為 \(m\))
B x y 表示在島 \(x\) 與島 \(y\) 之間修建一座新橋，
Q x k 表示詢問當前與島 \(x\) 連通的所有島中第 \(k\) 重要的是哪座島，即所有與島 \(x\) 連通的島中重要度排名第 \(k\) 小的島是哪座，請你輸出那個島的編號，
保證 \(1 \leq m \leq n \leq 10^5\), \(1 \leq q \leq 3 \times 10^5\)，\(p_i\) 為一個 \(1 \sim n\) 的排列，\(op \in \{\texttt Q, \texttt B\}\)，\(1 \leq u, v, x, y \leq n\)，
線段樹合并+并查集
如果只有操作 B ，那么不難用并查集完成，可是有了 Q 就不一樣，
我們可以用權值線段樹維護區間第K大，然后合并用線段樹合并+并查集，
時間復雜度 \(O(n+m\log n+ q\log n)\)，
線段樹與其他資料結構/演算法的比較
樹狀陣列
線段樹和樹狀陣列的時間復雜度大致相同，但是樹狀陣列的常數小，
線段樹比樹狀陣列難寫一些，但是樹狀陣列的思維性更加強，
樹狀陣列需要滿足可減性，線段樹不需要（這直接說明樹狀陣列無法完成RMQ操作），
樹狀陣列實作逆序對等更容易，線段樹需要實作權值線段樹，
線段樹可以方便地進行拓展，樹狀陣列比較困難，
ST表
ST表不支持修改，線段樹支持，
ST表的復雜度比線段樹更加優秀，
ST表需要冪等律，線段樹不需要，
線段樹可以方便地進行拓展，ST表比較困難，
分塊
分塊復雜度不如線段樹優秀，
線段樹需要結合律，分塊不需要，
莫隊
莫隊需要強制離線，線段樹不需要，
莫隊擅長的操作與線段樹擅長的操作不一樣，
線段樹時間復雜度比莫隊優秀，
如果文章有問題，靜待斧正，建議向我發送洛谷私信并指出博文地址 https://www.cnblogs.com/zheyuanxie/p/segment-tree.html！轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501351.html
標籤：其他