# 線段樹 ## 用途 在區間運算時如果我們使用陣列，單點修改是$O(1)$區間查詢是$O(N)$，而前墜和單點修改$O(N)$區間查詢$O(1)$。而線段樹可以做到單點修改和區間查詢都是$O(logn)$，甚至是區間修改區間查詢都$O(logn)$ ## 使用時機 在多次的區間運算(ex區間和、區間乘積、區間最大、最小)時 可以將$O(TN)$的時間複雜度降到$O(TlogN)$ ## 結構 線段樹是一個完全平衡二元樹，每個父節點都會有兩個子節點，而父節點會儲存兩個子節點的區間狀態(以區間和來說父節點就是儲存兩個子節點的和，而區間最大值就是存兩個子節點的max)，而把兩個子節點更新到父節點的操作我們稱之為pull，而兩個子節點的長度都分別是父節點的$1/2$(二分法) :::info 通常我們建陣列版線段樹時，陣列seg會以1-base操作(以seg[1]當根節點)，以方便實作 我們看圖可以發現假設存在一個節點seg[i]那麼它的子節點就會是seg[2 * i]和seg[2 * i + 1] (也可以寫成seg[i << 1]和seg[i << 1 | 1]) ::: ## 功能 - 單點查詢 區間查詢 - 單點修改 - 區間修改(要懶標記才能維持$O(logN)$) ## 實作 線段樹較常用於區間和，所以以下程式碼都以區間和示範 且範圍都是左閉右開 ### 建線段樹build ```cpp= #define m (l + r) >> 1 void build(int l = 0, int i = n, int i = 1){ if(r - l == 1){seg[i] = vc[l];return;} build(l, m, i << 1);build(m, r, i << 1 | 1); seg[i] = seg[i << 1] + seg[i << 1 | 1];//這就是pull } ``` ### 區間查詢query(單點) ```cpp= #define m (l + r) >> 1 int query(int ql, int qr, int l = 0, int r = n, int i = 1){ if(qr <= l || r <= ql){return 0;} if(ql <= l && r <= qr){return seg[i];} return query(ql, qr, l, m, i << 1) + query(ql, qr, m, r, i << 1 | 1); } ``` ### 單點修改 ```cpp= #define m (l + r) >> 1 void modify(int idx, int val, int l = 0, int r = n, int i = 1){ if(idx < l || r <= idx){return;} if(r - l == 1){seg[i] = val;return;} modify(idx, val, l, m, i << 1), modify(idx, val, m, r, i << 1 | 1); seg[i] = seg[i << 1] + seg[i << 1 | 1];//這也是pull } ``` ### 統整 ```cpp= #include<bits/stdc++.h> using namespace std; int n; const int N = 1e5+5; vector<int> seg(N << 2 + 5); vector<int> vc(N); #define m (l + r) >> 1 void build(int l = 0, int r = n, int i = 1){ if(r - l == 1){seg[i] = vc[l];return;} build(l, m, i << 1);build(m, r, i << 1 | 1); seg[i] = seg[i << 1] + seg[i << 1 | 1];//這就是pull } int query(int ql, int qr, int l = 0, int r = n, int i = 1){ if(qr <= l || r <= ql){return 0;} if(ql <= l && r <= qr){return seg[i];} return query(ql, qr, l, m, i << 1) + query(ql, qr, m, r, i << 1 | 1); } void modify(int idx, int val, int l = 0, int r = n, int i = 1){ if(idx < l || r <= idx){return;} if(r - l == 1){seg[i] = val;return;} modify(idx, val, l, m, i << 1), modify(idx, val, m, r, i << 1 | 1); seg[i] = seg[i << 1] + seg[i << 1 | 1];//這也是pull } #undef m int main(){ cin >> n; for(int i = 0; i < n; i++) cin >> vc[i]; build(); int T, op, l, r, x; int val; cin >> T; while(T--){ cin >> op; if(op){ cin >> l >> r; cout << query(l - 1, r) << '\n'; } else{ cin >> x >> val, modify(x - 1, val); } } //注意本身陣列是 0-base } ``` ## 懶標記 學完線段樹，我們可以發現線段樹在查詢時只要節點包含的區間在查詢範圍內就回傳，不再向下，所以我們其實可以把更改線段時的操作存在上面的節點(可以多開一個陣列tag)，當我們要對線段操作時在將儲存的tag向下推到左右子結點，並更新當前結點。(解講簡單點就讓你的程式偷懶，更新時不要向下傳，就存在最上面，只有當要用到下面子節點時才把懶標記推到下面，假設我們有一個長度為4的線段，那我們把0到3都加1，那就在根結點的tag陣列+1，查詢時就只要多加上(r-l)*tag就好了) ## 實作 懶標記的實作就是多了一個$push$，就是要對樹查詢或是更新時，就將$tag$的值更新回$seg$裡(以區間和來說，就是$+(r-l)*tag$)，並將$tag$向下推到子節點。 ```cpp= void push(int l, int r, int i){ if(!tag[i]) return; if(r - l == 1) {seg[i] += tag[i], tag[i] = 0; return;} seg[i] += (r - l) * tag[i]; tag[i << 1] += tag[i], tag[i << 1 | 1] += tag[i], tag[i] = 0; } ``` ## 統整(區間和) 有了懶標記，我們就可以在$O(logN)$實現區間查詢區間修改了 ```cpp= #include<bits/stdc++.h> using namespace std; int n; const int N = 1e5+5; vector<int> seg((N << 2) | 1); vector<int> tag((N << 2) | 1); vector<int> vc(N); #define m (l + r) >> 1 void build(int l = 0, int r = n, int i = 1){ if(r - l == 1) {seg[i] = vc[l]; return;} build(l, m, i << 1), build(m, r, i << 1 | 1); seg[i] = seg[i << 1] + seg[i << 1 | 1]; } void push(int l, int r, int i){ if(!tag[i]) return; if(r - l == 1) {seg[i] += tag[i], tag[i] = 0; return;} seg[i] += (r - l) * tag[i]; tag[i << 1] += tag[i], tag[i << 1 | 1] += tag[i], tag[i] = 0; } int query (int ql, int qr, int l = 0, int r = n, int i = 1){ push(l, r, i); if(qr <= l || r <= ql) return 0; if(ql <= l && r <= qr) return seg[i]; return query(ql, qr, l, m, i << 1) + query(ql, qr, m, r, i << 1 | 1); } void modify(int ql, int qr, int val, int l = 0, int r = n, int i = 1){ push(l, r, i); if(qr <= l || r <= ql) return; if(ql <= l && r <= qr) {tag[i] += val, push(l, r, i); return;} modify(ql, qr, val, l, m, i << 1), modify(ql, qr, val, m, r, i << 1 | 1); seg[i] = seg[i << 1] + seg[i << 1 | 1]; } #undef m int main(){ int T, op, l, r; int val; cin >> n; for(int i = 0; i < n; i++) cin >> vc[i]; cin >> T; build(); while(T--){ cin >> op >> l >> r; if(op){ cout << query(l - 1, r) << '\n'; } else{ cin >> val; modify(l - 1, r, val); } } } ``` :::info 可以想想如果線段樹是存max或是要算區間乘積時懶標記要怎麼辦呢 :::