線段樹 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 大小

$\le$ 原陣列大小的 4 倍

操作

• 區間查詢、單點查詢
• 單點修改
• 區間修改 (要用懶標記才比較快，Segment Tree 2 會講)

---

實作

很多時候是解區間和，因此以下範例為區間和線段樹

建線段樹

從大線段建到小線段比較簡單，因此我們 code 建議也是先使用這種

至於小線段建到大線段，留待各位自行研究。

對於欲操作陣列 v，使用遞迴建出 v 的線段樹，傳入引數有：

1. l：當前線段左界
2. r：當前線段右界 (左閉右開，實際上並不包含 v[r])
   $\Rightarrow$ 每個線段範圍可表示為
   $[l,r)$
3. i：當前線段的 key

當 r - l = 1 時，代表線段寬度剩

$1$，此時不用在二分下去，需 return

因此：

#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{array}{l}seg[i]ifql\le l<r\le qr\\ 0ifqr\le lorql\ge r\\ query(l,m)+query(m,r)else\end{array}}$

因此可以寫成：

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() 的最後一行會非常相似。

實作：

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];
}

整合

陣列版線段樹 (一般情況都是用這個)：

#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
}

指標版：動態開點再說

例題：DDJ a041. 奇怪的老闆

• 題目連結: a041: 奇怪的老闆

• 給定

  $1$ ~
  $n$ 位員工的薪水，求
  $l$ ~
  $r$ 位員工中，最高薪和最低薪的薪水差為何？

• (

  $n\le 5\times {10}^4,1\le l\le r\le n,$ 詢問次數
  $\le 2\times {10}^5$)

算是一個很經典的線段樹題，建兩個線段樹，

分別為「區間最大值」和「區間最小值」的線段樹，本題輕鬆解決。

code

#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;
}