---
type: slide
---
<style>
.reveal .slides {
text-align: left;
font-size:35px;
}
</style>
## 線段樹(2)
Introduction to Competitive Programming
2/17
----
- 懶人標記
- 基礎區間修改應用
- 更多變化應用
---
### 區間更新區間詢問
給一長度為 n 的整數序列，和 m 筆操作
操作分兩種
1. $\text{update l r v}$，將序列的區間 [l, r] 加值 v
2. $\text{query l r}$，詢問序列的區間 [l, r] 總和
$n,m<10^5$
----
### 使用單點修改線段樹
單點修改 [l , r] 範圍
時間複雜度最差的情況下，如果每次都加值整個序列，
為 $O(n\log n)$
修改 m 次，時間複雜度 $O(mn\log n)$，
比直接修改原陣列 $O(mn)$ 還差！
----
### 懶人標記 lazy tag
懶人標記的思想就是，如果所在的區間被修改的區間完全覆蓋的話，就在當前的區間打一個標記，代表這個區間以及下面所有區間都需要修改。
如果加值[0,6] 可以發現 [0,3] [4,5] [6,6] 以下的區間都要修改
----
多開一個陣列 tag 紀錄這個區間以及以下都要加值
```cpp=
void update(int id,int l,int r,int ql, int qr, int v){
if(ql <= l && r <= qr){ //如果當前區間被更新區間完全覆蓋到
tag[id] += v; //就打標記紀錄以下區間都要更新
return;
}
int mid=(l+r)>>1;
if(ql <= mid)
update(cl(id),l,mid);
if(qr > mid)
update(cr(id),mid+1,r);
pull(id, l, r);
}
```
----
### 懶人標記 lazy tag
可以發現使用懶人標記的修改會變的跟本來的查詢很像，都是所在區間被要求的區間完全覆蓋時，就打標記 $\to$ 回傳，所以 code 其實也差不多。
----
### push 函數
打上標記之後，下次經過這些節點時再更新節點，
並且將標記往下推。
因此在 update, query 函數最前面多一行 push
```cpp=
void push(int i, int l, int r) {
if(tag[i]) {
seg[i] += tag[i] * (r - l + 1); // 更新區間 [l, r]
if(l != r) { // 把標記往下推
tag[cl(i)] += tag[i];
tag[cr(i)] += tag[i];
}
tag[i] = 0; // 更新完區間後，把標記歸 0
}
}
void update(int id,int l,int r,int ql, int qr, int v){
push(id, l, r);
...
}
int query(int id,int l,int r,int ql,int qr){
push(id, l, r);
...
}
```
----
但這樣會發現上面的節點(紅色)也需要更新，
而更新就在 `update` 函數打完標記之後，回傳時順便更新即可
----
### pull 函數更新區間
```cpp=
void update(int id,int l,int r,int ql, int qr, int v){
if(ql <= l && r <= qr){
tag[id] += v;
return;
}
int mid=(l+r)>>1;
if(ql <= mid)
update(cl(id),l,mid, ql, qr, v);
if(qr > mid)
update(cr(id),mid+1,r, ql, qr, v);
pull(id, l, r); // 更新所有遍歷到的區間
}
```
----
### pull 函數
更新當前節點，則需要先把左右子節點都更新
再拿來更新自己
```cpp=
void pull(int i, int l, int r) {
int mid = (l+r)>>1;
push(cl(i), l, mid);
push(cr(i), mid + 1, r);
seg[i] = seg[cl(i)] + seg[cr(i)];
}
```
----
### 更新範例程式碼
```cpp=
void update(int i, int l, int r, int ql, int qr, int v){
push(i, l, r); // 懶標下推
if(ql <= l && r <= qr) {
tag[i] += v;
return;
}
int mid = (l + r)>>1;
if(ql <= mid)
update(cl(i), l, mid, ql, qr, v);
if(qr > mid)
update(cr(i), mid + 1, r, ql, qr, v);
pull(i, l, r); // 更新當前區間的總和
}
```
----
### 查詢
對於查詢其實操作是跟單點修改線段樹差不多的，
只是記得每次詢問前先記得把懶人標記更新並往下推。
----
跟單點修改線段樹相比
多一行 ```push``` 函數來更新節點並把懶人標記往下推
```cpp=
int query(int i, int l, int r, int ql, int qr) {
push(i, l, r);
if(ql <= l && r <= qr) {
return seg[i];
}
int mid = (l + r) / 2, ret = 0;
if(ql <= mid)
ret += query(cl(i), l, mid, ql, qr);
if(qr > mid)
ret += query(cr(i), mid + 1, r, ql, qr);
return ret;
}
```
---
## 例題時間
----
使用線段樹通常有兩個條件
- 當前節點維護的資訊可以從左右子節點得到
- 操作有結合率
就能用線段樹維護
----
### 例題：[CSES: Polynomial Queries](https://cses.fi/problemset/task/1736/)
給一個長度為 n 的整數序列，和 m 筆操作
操作分兩種
* $\text{0 l r}$ : 將區間 [l, r] 範圍的元素 $a_l$ 加 1， $a_{l+1}$ 加 2 ... 以此列推
* $\text{1 l r}$ : 詢問區間 [l, r] 的總和
至於這題要如何維護呢？ 🥴
----
詢問為求區間總和，
因此只需要把等差加值好好的處理就做完了
----
可以發現，我們對區間的加值會是一個從 1 開始、公差為 1 的等差數列，我們便可以維護這個性質，因為只要有首項、項數、公差，就可以在 $O(1)$ 時間算出等差數列的總和（高中數學）。
----
項數就是那個區間的大小，而當一個等差數列疊加到另外一個等差數列上時
```cpp
1 2 3 4 5 6
+ 1 2 3 4 5 6
_______________________
1 3 5 7 9 11 6
‾ ‾ ‾ ‾ ‾‾
```
可以發現重疊的部分的首項跟公差就會變成兩者相加了！
中間重疊部分的公差直接就變成 2，我們只需要維護這些，就可以解出這題了。
----
### 懶人標記下推
下推時，右子區間的首項要再加上左子區間的長度*公差
first 陣列紀錄當前區間第一個元素(首項)要加值多少
diff 陣列紀錄公差
```cpp=
int diff[MXN<<2], first[MXN<<2], seg[MXN<<2];
void push(int id, int l, int r){
if(diff[id]){
// (首項+末項) * 項次 / 2
seg[id] += (first[id]*2 + (r-l)*diff[id]) * (r-l+1) / 2;
if(l != r){
diff[cl(id)] += diff[id];
diff[cr(id)] += diff[id];
first[cl(id)] += first[id];
first[cr(id)] += first[id] + ((l+r)/2 - l + 1) * diff[id];
}
diff[id] = first[id] = 0;
}
}
```
----
### 區間更新 --- 打懶人標記
由於每次加的首項固定是 1，因此遞迴時不需要傳遞加值的參數
打懶人標記時，再判斷跟加值左界差多少即可
```cpp=
void update(int i, int l, int r, int ql, int qr){
push(i, l, r); // 懶標下推
if(ql <= l && r <= qr) {
first[i] += (l - ql + 1); // 區間首項加的值為當前左界 - 詢問左界 + 1
diff[i]++;
return;
}
int mid = (l + r)>>1;
if(ql <= mid)
update(cl(i), l, mid, ql, qr);
if(qr > mid)
update(cr(i), mid + 1, r, ql, qr);
pull(i, l, r); // 更新當前區間的總和
}
```
----
### 區間詢問
跟一般的總和線段樹沒什麼差別
seg 陣列一樣是儲存區間總和
不特別贅述
----
## [Range Updates and Sums](https://cses.fi/problemset/task/1735)
給一長度為 n 的整數序列，和 m 筆操作
操作分**三種**
1. $\text{update l r v}$，將序列的區間 [l, r] 加值 v
2. $\text{update l r v}$，將序列的區間 [l, r] 都設值成 v
3. $\text{query l r}$，詢問序列的區間 [l, r] 總和
$n,m<10^5$
多了一個區間設值
----
兩種操作單獨出現都可以解掉，但同時出現時要好好處理。
由於需要維護兩種懶標，我們還需要考慮同時有兩個懶標存在的情況。
----
兩個懶人標記 setTag 和 addTag
分別維護區間設值與區間加值
在維護標記時，可以分為 3 種情況
1. 本來沒有任何標記，現在再加值/設值
2. 本來有加值/設值標記，現在再加值
3. 本來有加值/設值標記，現在再設值
----
### 1. 本來沒有任何標記，現在再加值/設值
那就跟一般加值/設值線段樹一樣
打上加值或設值標記就好
----
### 2. 本來有加值/設值標記，現在再加值
- 本來有加值標記，那再加值有疊加性，不影響
- 本來有設值標記再加值，可以先設值完之後再加值
----
### 3. 本來有加值/設值標記，現在再設值
區間設值則之前所有的標記都要不用理他了
直接把原本的加值/設值都清空，設上新的值
----
綜合以上的 case，只需要好好處理以下情況
1. 更新區間時，同時有設值/加值標記時，先設值再加值
2. 有設值操作時，到覆蓋的區間先把原有的設值/加值標記先清空，再放上設值標記
其他跟一般線段樹相同 !
----
把這份講義的內容好好理解完能自己刻出來的話，
理論上線段樹實做就不會有什麼問題了
夠熟的話也能跟講師一樣，無腦三分鐘內刻完區間修改線段樹
----
剩下的就是應付各種題目的題目變化
題目主要有兩種
1. 轉換題意，配合基礎的加值/求區間總和或極值(題單的D)
2. 維護的東西與平常不同，好好維護懶人標記以及合併(題單的C,E)
----
而 BIT 的 code 比 segment tree 短很多，
遇到資料結構題時，請先想一下 BIT 是否可做(區間修改/單點詢問 or 單點詢問/區間修改)
如果可以的話請不要沒事亂砸線段樹
實作量較大，bug 可能也比較多
----
[題單](https://vjudge.net/contest/604328)
Google Drive
Gist
Clipboard
Sign in with Wallet
