---
# System prepended metadata

title: Segment Tree 2
tags: [2024-winter]

---

---

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
懶人標記的思想就是，如果所在的區間被修改的區間完全覆蓋的話，就在當前的區間打一個標記，代表這個區間以及下面所有區間都需要修改。
![image](https://hackmd.io/_uploads/By2aqnA56.png =700x)
如果加值[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` 函數打完標記之後，回傳時順便更新即可

![image](https://hackmd.io/_uploads/rkNUwC05a.png)

----

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