---
tags: 進階班
---
# 線段樹 Segment tree 2

## 本次範圍

懶標記、動態開點

## 前言

上次說過懶標記可以**區間修改**，這次就來介紹！

而離散化技巧可以有效壓縮線段樹的大小，有時候是必要手段

## 懶標記

如果使用單點修改的方式做區間修改，時間複雜度為 $O(KlgN)\Rightarrow$ 超慢

($K = r - l$ )

對於區間修改，以一個題目來說，有時我們修改一個區間，但後來題目並不會詢問到那一個區間，

那麼，~~幹嘛改阿~~

這時，我們可以利用「標記」 `tag[i]` 來紀錄哪些是「待改」的線段。

流程如下：

#### 修改時

1. 在修改時，先把欲修改的值加入 `tag[i]`
2. **把「欲修改的線段」的父線段及本身線段先修改**

要先修改父線段和自己的原因是因為 `query()` 時，可能只會搜尋到大線段，

如果小線段的修改值沒有傳給大線段，那麼就會 `NA`。
3. 如果目前遍歷到的線段，其 `tag[i]` 值不為 $0$，則也要修改線段。

(可能是前面的修改遺留下來的)

因此，`modify()` 會變成：

void modify(int ql, int qr, LL val, int l = 0, int r = n, int i = 1){
	/*修改線段*/
	if(qr <= l || r <= ql) return;
	if(ql <= l && r <= qr) {tag[i] += val, /*修改線段*/; 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];
}

#### 查詢時

跟原本幾乎相同，只是在傳回值之前，也要把該線段的 `tag[i]` 清空。

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

所以，**到底怎麼修改線段，又能把還沒修改的值留下來呢？**

其實就只要把 `tag[i]` 清空，修改 `seg[i]`，(修改值為 `(r - l) * tag[i]`)

然後把 `tag[i]` 的值傳到 `tag[i << 1]`、`tag[i << 1 | 1]` 就好了

這個函數會取名為 `push()` 因為很像把懶標記「推」到下方節點

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

#### 整合

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
int maxn = 2e5 + 1, n;
vector<LL> v(maxn), tag((maxn << 2) | 1), seg((maxn << 2) | 1);
#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];
}
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;
}
LL query (int ql, int qr, int l = 0, int r = n, int i = 1){
	push(l, r, i);
	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 ql, int qr, LL 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; LL val;
	cin >> n >> T;
	for(int i = 0; i < n; i++) cin >> v[i];
	build();
	while(T--){
		cin >> op >> l >> r;
		if(op) cout << query(l - 1, r) << '\n';
		else cin >> val, modify(l - 1, r, val);
	}
}

---

## 動態開點

有些題目很糟糕，需要陣列開 $10^8$ 的大小，顯然不行，記憶體會爆掉。

(陣列要**一次開完所有節點**)

但是這種題目都會有一個特點：**操作次數很少**

這時可以用指標，要用的節點再開，雖然**單一節點的記憶體肥**，但**整體來說還是贏陣列很多**的

$\Rightarrow$ 新增一個陣列值最多要開 $lg(maxn)$ 個節點，

如果導的出這個結論，那麼想法就應該對了。

### 實作

#### 節點 node

就是線段樹上的每個線段，每個線段都有：

1. 本身的值 `v`
2. 自身的左、右子節點 `l, r`

整個 `node` 可以包裝成一個 `struct`

我們可以在宣告 `struct` 的同時也宣告線段樹的根節點 `root`

而在以下操作中，節點的初始化都是 `nullptr`，避免不必要的記憶體消耗

struct node {
	int v; node *l, *r;
}*root = nullptr;

#### 建立線段樹 build()

由於我們是要用到節點再開，因此**沒有 `build()`**

#### 遍歷 query()

和原本的線段樹雷同，不過：

1. 左節點的 `index` 從 `i << 1` 變成 `cur -> l`
2. 右節點的 `index` 從 `i << 1 | 1` 變成 `cur -> r`
3. 原先的傳回值從 `seg[i]` 變成 `cur -> v`
4. 由於是動態開點，可能存在 「目前節點不存在的問題」，判斷時要注意。

int query(int ql, int qr, node* cur = root, int l = 0, int r = n) {
	if (!cur || qr <= l || r <= ql) return 0; //!cur : 判斷是否有此節點
	if (ql <= l && r <= qr) return cur -> v;
	return query(ql, qr, cur -> l, l, m) + query(ql, qr, cur -> r, m, r);
}

#### 更新 update() (modify() 也是一樣的意思)

這裡講單點修改

也是跟原本陣列版的 update() 雷同，不過注意的地方和 query() 一樣

而且 update() 多了 「節點不存在就要創立」 這件事

因為 query() 遇到沒有節點時就是代表該節點是 $0$，根本不用算

但 update() 遇到沒節點...就是要更新線段樹

因此：

void update(int p, int x, node* &cur = root, int l = 0, int r = n) {
	if (p < l || r <= p) return;
	if (!cur) cur = new node {0, nullptr, nullptr}; //建立新節點
	cur -> v += x;
	if (r - l == 1) return;
	update(p, x, cur -> l, l, m), update(p, x, cur -> r, m, r);
}

所以說 `node* &cur` 是甚麼神操作？

:::spoiler `answer`
`node*` 是指標的型態，`&` 是參照，加了才能更改節點內的值
:::

#### 整合

#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int n = 1e8 + 5;
struct node {
	int v; node *l, *r;
}*root = nullptr;
#define m ((l + r) >> 1)
void update(int p, int x, node* &cur = root, int l = 0, int r = n) {
	if (p < l || r <= p) return;
	if (!cur) cur = new node {0, nullptr, nullptr};
	cur -> v += x;
	if (r - l == 1) return;
	update(p, x, cur -> l, l, m), update(p, x, cur -> r, m, r);
}
int query(int ql, int qr, node* cur = root, int l = 0, int r = n) {
	if (!cur || qr <= l || r <= ql) return 0;
	if (ql <= l && r <= qr) return cur -> v;
	return query(ql, qr, cur -> l, l, m) + query(ql, qr, cur -> r, m, r);
}
#undef m
int main() {
	int T, op, key, val, l, r;
	cin >> T;
	while (T--) {
		cin >> op;
		if (op) cin >> key >> val, update(key, val);
		else cin >> l >> r, cout << query(l, r + 1) << '\n'; //這裡是 [l, r]
	}
	return 0;
}

---

## 小結

題目不搞怪，用線段樹模板

題目要你開超大陣列，用動態開點

題目要你區間修改，用懶標記

題目要區間修改又要開超大陣列，先想想有沒有更好的算法，沒有就...懶標記與動態開點整合...

或許比賽中放棄也是不錯的選擇 (怕你解這題的時間成本太高)

## 題目練習：DDJ a408 & a522

1. 題目連結：[a408: 區間更新](http://203.64.191.163/ShowProblem?problemid=a408)

- 兩個操作：對一區間的所有值 $+k$，或是詢問 $[l, r]$ 區間和。

因為跟懶標記的範例程式碼太像，所以這邊就不貼了。

2. 題目連結：[a522: Mining for Gold (hard version)](http://203.64.191.163/ShowProblem?problemid=a522)

- 兩個操作：單點值 $+1$ 或詢問 $[l, r]$ 區間和，不過 $[l, r]$ 範圍有夠大

不過對動態開點來說，這只不過是個模板題 :poop:

:::spoiler `code`

#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int n = 1e8 + 5;
struct node {
	int v; node *l, *r;
}*root = nullptr;
#define m ((l + r) >> 1)
void update(int p, int x, node* &cur = root, int l = 0, int r = n) {
	if (p < l || r <= p) return;
	if (!cur) cur = new node {0, nullptr, nullptr};
	cur -> v += x;
	if (r - l == 1) return;
	update(p, x, cur -> l, l, m), update(p, x, cur -> r, m, r);
}
int query(int ql, int qr, node* cur = root, int l = 0, int r = n) {
	if (!cur || qr <= l || r <= ql) return 0;
	if (ql <= l && r <= qr) return cur -> v;
	return query(ql, qr, cur -> l, l, m) + query(ql, qr, cur -> r, m, r);
}
#undef m
int main() {
	cin.tie(nullptr), ios_base::sync_with_stdio(false);
	int T, op, k, a, b;
	cin >> T;
	while (T--) {
		cin >> op;
		if (op == 1) cin >> k, update(k, 1);
		else if (op == 2) {
			cin >> a >> b; 
			cout << query(a, b + 1) / 6 * 48 << '\n';
		} 
	}
	return 0;
}

:::