--- tags: algorithm --- # 線段樹 線段樹，又稱Segment tree, 簡單來說就是來存線段的 也可以方便的修改和球區間和，那要怎麼做呢　$\implies$　分組 如果有一個區間 ```graphviz digraph main{ node[shape = rect] 1 2 3 4 } ``` 先兩兩一組 ```graphviz digraph main { node[shape = rect] "(1, 2)" -> {1 ,2} "(3, 4)" -> {3, 4} } ``` 再把兩組合併為組 ```graphviz digraph main { node[shape = rect] "(1, 4)" -> {"(1, 2)", "(3, 4)"} "(1, 2)" -> {1, 2} "(3, 4)" -> {3, 4} } ``` 可以用指標或著陣列存 用指標存實作比較直觀，一些神奇的操作也大多用指標，不過佔的記憶體比較大。 實作的話也有分`左閉又閉` 和`左閉右開`，不過為方便理解，這裡用左閉右閉來實作 ## 指標實作 ### 節點 有左節點和右節點, ```cpp = struct node { node *l, *r; node val; node(int k = 0) : val(k) {l = r = nullptr;} void pull() {val = (l ? l -> val : 0) + (r ? r -> val : 0);} } ``` --- ### 操作 #### 建樹 `void build(node *& cur, int l = 1, int r = mxN) ` 如果需要預先建樹的話還是會用陣列比較方便，不過這邊還是放個程式碼 ```cpp = void build(node *& cur, int l = 1, int r = mxN) { if(!cur) cur = new node(0); if(l == r) {cur -> val = ar[l]; return;} int m = (l + r) >> 1; build(cur -> l, l, m); build(cur -> r, m + 1, r); cur -> pull(); } ``` #### 更新 ```cpp = void pull() { val = (l ?l -> val :0) + (r ? r -> val : 0) } ``` --- #### 修改 `void upd(node *& cur, int pos, int val, int l = 1, int r = mxN)` ```cpp = void upd(node *& cur, int pos, int val, int l =1, int r = mxN) { if(!cur) cur = new node(); if(pos > r || pos < l) return; if(l == r) {cur -> val = val; return;} int m = (l + r) >> 1; upd(cur -> l, pos, val, l, m); upd(cur -> r, pos, val, m + 1, r); cur -> pull(); } ``` --- #### 查詢 `int qry(node *cur, int ql, int qr, int l = 1, int r =mxN)` ```cpp = int qry(node *cur, int ql, int qr, int l = 1, itn r = mxN) { if(!cur) return 0; if(ql <= l && r <= qr) return cur -> val; int m = (l +r) >> 1; return qry(cur -> l, ql, qr, l,, m) + qry(cur -> r, ql, qr, m + 1, r); } ``` --- ## 陣列實作 ### 操作 :::success $$lc(id) = id << 1;$$ $$rc(id) = id << 1|1;$$ ::: #### 更新 `void upd(int id)` ```cpp = void pull(int id) { seg[id] = seg[lc(id)] +seg[rc(id)] } ``` --- #### 建樹 `void build(int l = 1, int r = mxN, int id = 1)` ``` cpp = void build(int l = 1, int r = mxN, int id = 1) { if(r == l) {seg[id] = ar[l]; return;} int m = (l + r) >> 1; upd(l, m, lc(id)); upd(m +1, r, rc(id)); pull(id); } ``` --- #### 修改 `void upd(int pos, int k, int l = 1, int r = mxN, int id = 1)` ```cpp = void upd(int pos, int k, int l = 1, itn r = mxN, int id = 1) { if(pos > r || pos < l) return; if(l == r) { seg[id] = k; return; } int m = (l +r ) >> 1; upd(pos, k, l, m, lc(id)); upd(pos, k, m + 1, r, rc(id)); pull(id); } ``` --- #### 查詢 `int qry(int ql, int qr, int l = 1, int r = mxN, int id = 1)` ``` cpp = int qry(int ql, int qr, int l = 1, int r = mxN, int id = 1) { if(l > qr || r <ql) return 0; if(ql <= l && r <= qr) return seg[id]; int m = (l +r) >>1; return qry(ql, qr, l, m, lc(id)) + qry(ql, qr, m + 1, r, rc(id)); } ``` ```cpp = #define lc(id) id << 1 #define rc(id) id << 1|1 const int mxN = 1e6 + 1; int seg[mxN << 2], ar[mxN]; // mxN << 2 == mxN * 4 void build(int l = 1, int r = mxN, int id = 1) { if(l == r) {seg[id] = ar[l]; return;} int m = (l + r ) >> 1; // (l + r) / 2 build(l ,m, lc(id)); build(m + 1, r, rc(id)); seg[id] = seg[lc(id)] + seg[rc(id)]; } void upd(int pos, int val, int l = 1, int r = mxN, int id = 1) { if(pos < l || r < pos) return; if(l == r) {seg[id] = val; return;} int m = (l + r) >> 1; upd(pos, val, l, m, lc(id)); upd(pos, val, m + 1, r, rc(id)); seg[id] = seg[lc(id)] + seg[rc(id)]; } int qry(int ql, int qr, int l = 1, int r = mxN, int id = 1) { if(ql > r || qr < l) return 0; if(ql <= l && r <= qr) return seg[id]; int m = (l + r) >> 1; return qry(ql ,qr, l, m, lc(id)) + qry(ql, qr, m + 1, r, rc(id)); } ``` --- ### 複雜度 ***建樹:*** $複雜度O(N)$ ***單點修改 :***　$複雜度O(\log N)$ ***區間求值 :*** $複雜度O(\log N)$