---
tags: 進階班
---
# 線段樹 Segment tree 1
## 本次範圍
陣列版線段樹 (區間查詢、單點修改)
## 用途
對於區間運算 (e.g. 區間和、區間乘積、區間最大/最小) 可以更快速地運算
適合多次查詢時使用
可將複雜度從 $O(TN)$ 變為 $O(TlgN)$
## 結構
存下一個陣列特定區間的運算結果，並可用多個線段整合後表示出所有區段的答案
$\Rightarrow$ 區間長度是用二分法分出來的
示意圖：
通常我們建線段樹時，會以 1-base 操作(即不使用 `Seg[0]`)，不僅運作程式較快，寫起來也較方便
一個線段假設存於 `Seg[n]`，那麼二分後的線段通常會存在 `Seg[2*n], Seg[2*n+1]`
由示意圖，我們可以知道：**segment tree 大小 $\leq$ 原陣列大小的 4 倍**
## 操作
- 區間查詢、單點查詢
- 單點修改
- 區間修改 (要用懶標記才比較快，Segment Tree 2 會講)
---
## 實作
很多時候是解區間和，因此以下範例為區間和線段樹
### 建線段樹
從大線段建到小線段比較簡單，因此我們 `code` 建議也是先使用這種
至於小線段建到大線段，留待各位自行研究。
對於欲操作陣列 `v`，使用遞迴建出 `v` 的線段樹，傳入引數有：
1. `l`：當前線段左界
2. `r`：當前線段右界 (左閉右開，實際上並不包含 `v[r]`) $\Rightarrow$ 每個線段範圍可表示為 $[l, r)$
3. `i`：當前線段的 `key`
當 `r - l = 1` 時，代表線段寬度剩 $1$，此時不用在二分下去，需 `return`
因此：
```cpp=
#define m (l + r) >> 1
void build(int l = 0, int r = n, int i = 1){
if(r - l == 1) {seg[i] = v[l]; return;}
build(l, m, i << 1), build(m, r, i << 1 | 1);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
```
### 區間查詢
只要會區間查詢，顯然單點查詢不是問題。
在查詢時，應該有 `5` 個變數：
1. `ql`：欲查詢之左界
2. `qr`：欲查詢之右界
3. `l`：當前線段之左界
4. `r`：當前線段之右界
5. `i`：當前線段的 `key`
查詢時，一樣使用遞迴，且
$query(l, r)\displaystyle \begin{cases} seg[i]\quad\quad\quad\quad\quad\quad\;\;\;\quad\quad\quad\quad if\quad ql\leq l < r\leq qr\\0\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;\; if\quad qr \leq l\quad or\quad ql\geq r \\ query(l, m) + query(m, r)\quad\quad else\end{cases}$
因此可以寫成：
```cpp=7
LL query (int ql, int qr, int l = 0, int r = n, int i = 1){
if(qr <= l || r <= ql) return 0LL;
if(ql <= l && r <= qr) return seg[i];
return query(ql, qr, l, m, i << 1) + query(ql, qr, m, r, i << 1 | 1);
}
```
### 單點修改
若今天沒有「修改」，那麼區間和就可以用前綴和解決，顯然比較輕鬆。
\
若今天要使 `arr[x] = new value`，很簡單，只要查到 $[x, x + 1)$ 存於哪一個 `seg[i]` 即可
$\Rightarrow$ 查詢線段的動作和 `query()` 滿相似的，只是要根據「單點」性質做一些微調
\
因為改變了 `arr[x]`，因此所有包含 `arr[x]` 的 `seg[i]` 都必須更新
$\Rightarrow$ `modify()` 和 `build()` 的最後一行會非常相似。
實作：
```cpp=12
void modify(int x, LL val, int l = 0, int r = n, int i = 1){
if(x < l || r <= x) return;
if(r - l == 1) {seg[i] = val; return;}
modify(x, val, l, m, i << 1), modify(x, val, m, r, i << 1 | 1);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
```
### 整合
陣列版線段樹 (一般情況都是用這個)：
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int maxn = 2e5, n;
vector<LL> v(maxn + 1), seg((maxn << 2) + 5);
#define m (l + r) >> 1
void build(int l = 0, int r = n, int i = 1){
if(r - l == 1) {seg[i] = v[l]; return;}
build(l, m, i << 1), build(m, r, i << 1 | 1);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
LL query (int ql, int qr, int l = 0, int r = n, int i = 1){
if(qr <= l || r <= ql) return 0LL;
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 x, LL val, int l = 0, int r = n, int i = 1){
if(x < l || r <= x) return;
if(r - l == 1) {seg[i] = val; return;}
modify(x, val, l, m, i << 1), modify(x, val, m, r, i << 1 | 1);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
#undef m
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> v[i];
build();
int T, op, l, r, x; LL 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
}
```
指標版：動態開點再說 :poop:
## 例題：DDJ a041. 奇怪的老闆
* 題目連結: [a041: 奇怪的老闆](http://203.64.191.163/ShowProblem?problemid=a041)
* 給定 $1$ ~ $n$ 位員工的薪水，求 $l$ ~ $r$ 位員工中，最高薪和最低薪的薪水差為何？
* ($n\leq 5\times 10^4, 1\leq l\leq r\leq n,$ 詢問次數 $\leq 2\times 10^5$)
算是一個很經典的線段樹題，建兩個線段樹，
分別為「區間最大值」和「區間最小值」的線段樹，本題輕鬆解決。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int MxN = 5e4;
vector<int> v(MxN + 1), hseg((MxN << 2) + 5), lseg((MxN << 2) + 5);
#define m ((l + r) >> 1)
void build(int i = 1, int l = 0, int r = MxN) {
if (r - l == 1) {hseg[i] = lseg[i] = v[l]; return;}
build(i << 1, l, m), build(i << 1 | 1, m, r);
hseg[i] = max(hseg[i << 1], hseg[i << 1 | 1]);
lseg[i] = min(lseg[i << 1], lseg[i << 1 | 1]);
}
int hquery(int ql, int qr, int i = 1, int l = 0, int r = MxN) {//maximum
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return hseg[i];
return max(hquery(ql, qr, i << 1, l, m), hquery(ql, qr, i << 1 | 1, m, r));
}
int lquery(int ql, int qr, int i = 1, int l = 0, int r = MxN) {//minimum
if (qr <= l || r <= ql) return 2147483647;
if (ql <= l && r <= qr) return lseg[i];
return min(lquery(ql, qr, i << 1, l, m), lquery(ql, qr, i << 1 | 1, m, r));
}
#undef m
int main() {
cin.tie(nullptr), ios_base::sync_with_stdio(false);
int n, m, l, r;
cin >> n >> m;
for (int x = 0; x < n; x++) cin >> v[x];
build();
while (m--) {
cin >> l >> r;
cout << hquery(l - 1, r) - lquery(l - 1, r) << '\n';
}
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet