---
tags: PCCA
---
# Segment tree (Advanced)
## Pre-knowledge
- 線段樹基本概念
- 懶標記使用方法
{%youtube Hfue-_pVFPc %}
<!-- ## 快速複習
TBD -->
---
## 指標動態開點線段樹
現在有一個題目
> 給定一個長度為 $N$ ，初始皆為 $0$ 的序列，共有 $Q$ 筆操作，每筆操作可能是
> 1. 修改第 $i$ 個位置的值成 $x$
> 2. 求 $[L,R)$ 區間內的和
>
> $1\leq N\leq 10^9\text{, }1\leq Q\leq 2\times 10^5$
> **輸入強制在線**
有學過基本的 BIT / 線段樹就會知道這就是簡單的區間和問題，但這題 $N$ 的範圍大了很多，不管是線段樹還是 BIT ，陣列直接開 $10^9$ 高機率會吃 MLE ，因為有強制在線所以無法提前知道哪些點會用到去做離散化，這時候就需要動態開點了。
對於每一個修改操作來說，總共只會改到約 $\lg N$ 個點，意思是就算 $N=10^9$ 實際上會動到，也就是非 $0$ 的點其實只有最多約 $Q\lg N \approx 6\times 10^6$ 個。
:::spoiler 示意圖 {state=open}
在這個例子中 $N=16$ , $Q=2$
可以看到實際有走訪到的節點總共只有 $9$ 個。
:::
如果我們實作線段樹的時候省略掉這些值為 $0$ ( i.e.沒有走訪過 ) 的點的話，就能讓空間複雜度從 $O(N)$ 降到 $O(Q\lg N)$ 了
### 動態開點線段樹實作
俗話說得好，有幾個人就有幾種線段樹實作方法，這裡只是提供我自己最常用的寫法，不代表只能這樣寫，像是左閉右開、左閉右閉、 0-base 、 1-base 之類的細節自己刻的習慣的方法就是好方法。
這裡我個人習慣左閉右開的方式來寫，所以以下的範例 code 區間都是左閉右開。
因為要動態開點，一開始不會確定到底哪些點會開到，所以線段樹就不能簡單的用陣列及位元運算儲存，對於每個節點需要額外儲存指向子節點的指標。
```cpp=
using ll=long long;
struct node{
node *l,*r;
ll val;
node():val(0){l=r=nullptr;}
void pull(){
val=0;
for(auto i:{l,r})
if(i) val+=i->val;
}
}*root=nullptr;
```
基本上修改和詢問就跟非動態開點版本的線段樹差別不大
不同的地方在於，在修改時如果遇到空節點就要動態配置一個新節點在那個位置
:::spoiler modify 示意圖 {state=open}
設 $N=16$ ，現在有兩筆 modify 操作：將第 $3$ 個位置改成 $5$ ，將 $11$ 的位置改成 $2$。
:::
```cpp=12
#define m ((l+r)>>1)
// pos: position to be modified
// val: value to substitude
void modify(int pos,int val,node*& cur=root,int l=0,int r=maxn){
if(pos<l||r<=pos) return;
if(!cur) cur=new node; // new node!
if(r-l==1){cur->val=val;return;}
modify(pos,val,cur->l,l,m),modify(pos,val,cur->r,m,r);
cur->pull();
}
```
而在查詢時如果遇到空節點就代表那個區間都沒有被動過，在這個例子中代表值都是 $0$
```cpp=22
// [ql,qr): the interval of query
ll query(int ql,int qr,node* cur,int l=0,int r=maxn){
if(qr<=l||r<=ql||!cur) return 0;
if(ql<=l&&r<=qr) return cur->val;
return query(ql,qr,cur->l,l,m)+query(ql,qr,cur->r,m,r);
}
#undef m
```
### 動態開點總結
- 在沒辦法離散化的區間問題可以用，將空間複雜度從 $O(N)$ 降到 $O(Q\lg N)$
- 實作上需要用指標記錄子節點，除此之外跟一般線段樹沒什麼差別
### 例題
- [CSES - Salary Queries](https://cses.fi/problemset/task/1144/)
---
## 持久化線段樹
現在有另一個題目 [CSES - Range Queries and Copies](https://cses.fi/problemset/task/1737)
> 給定一個長度為 $N$ 的序列，版本號為 $1$
> 共有 $Q$ 筆操作，每筆操作可能是
> 1. 修改第 $k$ 個版本裡第 $i$ 個位置的值成 $x$
> 2. 求第 $k$ 個版本內 $[L,R)$ 區間內的和
> 3. **將第 $k$ 個版本的內容複製一份，版本號設為目前版本數量$+1$**
>
> $1\leq N,Q\leq 2\times 10^5$
如果沒有第 $3$ 個操作很明顯是線段樹簡單題 (或是離線的話用前綴和就好了) 。如果每次出現操作 $3$ 都把整顆線段樹真的整個複製一份的話，那很明顯不管是時間複雜度跟空間複雜度都會是 $O(NQ)$ 等級，顯然不能接受。
但是如果仔細觀察線段樹在做各個操作後的改變，操作 $2,3$ 顯然不會對值造成改變，而操作 $2$ 其實只會動到最多約 $\lg N$ 個節點而已，那其實代表說在兩個版本之間假設做了 $k$ 個操作，那最多只會有約 $k\lg N$ 個節點和之前的版本不一樣而已。
:::spoiler 示意圖 {state=open}
這是一個有 $n=8$ 的線段樹，當我們要對其中的第 $3$ 個元素進行修改，所經過的節點如下圖：
所以我們可以用動態分配記憶體的方法，對於每次修改都新開樹高( $h$ )個點就好，再將沒有修改到的地方指回原本的節點。如下圖：
如果再修改第 $6$ 個點，如下圖
可以看到每次都會產生新的根節點，只要保存每個根節點就可以存取所有的版本。
:::
只額外儲存修改過的部分，這就是持久化線段樹的主要概念。
### 持久化線段樹實作
因為有很多節點會重複使用，節點間的關係比較複雜，基本上還是用指標版的線段樹做持久化，節點內要存左右節點的指標以及當前節點的值。另外，寫一個複製用的建構元，等等會用到。
```cpp=1
using ll=long long;
struct node{
node *l,*r;
ll val;
node(int x=0):val(x){l=r=nullptr;}
node(node* p){*this=*p;}
void pull(){
val=0;
for(auto i:{l,r})
if(i) val+=i->val;
}
};
```
如果初始值都是 $0$ 的話可以動態開點就好，但題目有給定初始陣列的話就需要 $O(N)$ 建構一下，不然如果用 `modify` 一個個改的話空間複雜度就會變成 $O((N+M)\lg N)$ ，稍微有點肥。
```cpp=13
// v: initial array
node* build(vector<int>& v,int l=0,int r=maxn){
if(r-l==1) return new node(v[l]);
node* ret=new node;
ret->l=build(v,l,m),ret->r=build(v,m,r);
return ret->pull(),ret;
}
```
因為任何有修改到的操作都會造成一個新的版本(和題目中的版本不一樣，這裡指的是線段樹內部的值改動)，因此就算這個操作在題目裡屬於同一個版本，修改時都要額外做出 $\lg N$ 個點才能保證前面的版本不被後面修改操作干擾到。
```cpp=20
// p: previous version of current node
// k: the position to be modified
// v: the value to be set
node* modify(node* p,int k,int v,int l=0,int r=maxn){
if(k<l||r<=k) return p;
if(r-l==1) return new node(v);
node* ret=new node;
ret->l=modify(p->l,k,v,l,m);
ret->r=modify(p->r,k,v,m,r);
return ret->pull(),ret;
}
```
詢問的話因為不涉及修改，所以就照一般的線段樹詢問就好了
```cpp=31
ll query(node* p,int ql,int qr,int l=0,int r=maxn){
if(qr<=l||r<=ql) return 0;
if(ql<=l&&r<=qr) return p->val;
return query(p->l,ql,qr,l,m)+query(p->r,ql,qr,m,r);
}
#undef m
```
### 例題
- [CSES - Range Queries and Copies](https://cses.fi/problemset/task/1737)
---
**以下為出現在 [Things I don't know](https://codeforces.com/blog/entry/92248) 裡的內容，僅適合已經將線段樹基礎應用都融會貫通或是對資結很有興趣且不特別在乎競程成績的人，否則去多寫點題會對你的競程實力有更大的幫助。**
## Segment tree beats
接下來考慮以下題目
> 給定一個長度為 $N$ ，共有 $Q$ 筆操作，每筆操作可能是
> 1. 將 $[L,R)$ 區間內的值都加上 $k$
> 2. **將 $[L,R)$ 區間內的值都做與 $k$ 做取 `min` 操作**
> 3. 求 $[L,R)$ 區間內的和
>
> 將 $a$ 與 $k$ 做取 `min` 操作指的是 `a=min(a,k)`
>
> $1\leq N,Q\leq 2\times 10^5$
如果沒有操作 $2$ 的話，就只是區間加值的問題，用簡單的懶標線段樹就可以解決了，但取 `min` 操作相較於一般的加值設值來說比較麻煩，因為區間內可能有些值會被改到，有些不會被改到。因為使用懶標的前提是能夠快速的計算出打上懶標後區間內值的改動，因此這個操作沒有辦法簡單的打個懶標就好。
這時候就可以利用 segment tree beats 的想法來解決，主要概念是每次做取 `min` 的時候都會將大於 $k$ 的值都設成 $k$ 所以就會讓區間內的最大值變小，同時也會降低區間內存在的值域。而只要分別維護區間最大值、區間次大值、區間最大值數量，就可以做出這個操作。
設 $mx$ 為區間最大值、 $smx$ 為區間次大值、 $mxcnt$ 為區間最大值數量、 $mxtag$ 為對區間最大值做區間增值的懶標
在修改時根據目前區間的最大值和次大值，分別做出以下操作
| Case | 操作 |
| ---------- | ---------------------------------------- |
| $mx<=k$ | 不做任何操作 |
| $smx<k<mx$ | 將 $mxtag$ 修改加上 $(k-mx)\times mxcnt$ |
| $k<=smx$ | 對左右節點遞迴下去繼續修改 |
分析後可以確定這樣做的時間複雜度上界至少會是 $O(Q\lg^2 N)$ ，詳細證明可以參考 [吉如一的區間最值操作與歷史最值問題](http://www.doc88.com/p-6744902151779.html)
這裡附上一份解 [Library Checker - Range Chmin Chmax Add Range Sum](https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum) 這個題目的 code ，因為時間問題沒有辦法給出完整的說明，有興趣的人可以自己點進去看。
[Pastebin Link](https://pastebin.com/uBJqDQq5)
---
<!-- ## 2d 線段樹 -->
Sign in with Wallet
Connect another wallet