## Pre-knowledge

### Binary search tree

一種二元樹狀結構，滿足以下性質
- 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值
- 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值
- 任意節點的左、右子樹也分別為二元搜尋樹

:::spoiler 一棵 BST {state=open}
:::

### Heap

可以參考去年的影片

{%youtube cdakZQa2pXE%}

簡單來說就是一種樹狀結構 (通常是二元)，滿足以下性質
- 給定堆積中任意節點P和C，若P是C的母節點，那麼P的值會小於等於（或大於等於）C的值

:::spoiler 一個最小堆 {state=open}
:::

### Segment tree (Optional)

可以參考去年的影片

{%youtube Hfue-_pVFPc %}

---

## 認識 Treap

### 什麼是 Treap

Treap 又叫做樹堆，是一種平衡二元搜尋樹 (Self-balancing binary search tree)
因為同時滿足 BST 和 Heap 的性質所以叫做 Treap (Tree + Heap)。

:::spoiler 一棵 Treap {state=open}

節點內左邊的值為 Tree key ，右邊的值為 Heap key

:::

根據實作方法分成基於旋轉以及基於 merge-split 的，在這裡只會介紹 merge-split 版本。

### Treap 的特色

- 實作簡單
- 擴充性高
- 能解決幾乎所有線段樹能做的區間問題(但常數比較大)
- 能做到一些線段樹很難做到的奇怪問題

---

## Treap 的實作

### Treap 的結構

Treap 需要讓兩個權值分別同時滿足 BST 和 Heap 的性質，因此節點內除了是顆二元樹都有的左右節點指標以外還至少會有一個 Tree key 跟 Heap key 。而 Heap key 是在建構時就給定一個範圍足夠大、足夠隨機的數字。

mt19937 mt(hash<string>()(":poop:"));  // C++ randomizer
struct node{
    node *l,*r;  // subtrees
    int tree_key,heap_key;
    node(int x):tree_key(x),heap_key(mt()){
        l=r=nullptr;
    }
};

### 基礎操作

Treap 基本上只有兩個基礎操作: Merge 跟 Split ，所有其他的操作都是由這兩個操作組合而成的。

#### Merge

Merge 要做的事情就是把 $a,b$ 兩顆 Treap 合併，其中 $a$ 樹中的所有 Tree key 值都小於等於 $b$ 樹中的 Tree key。

:::spoiler 兩棵 treap a,b {state=open}

藍色為 treap $a$ ，綠色為 treap $b$


:::

因為需要滿足 Heap 的性質，首先要根據 Heap key 決定誰要當根節點，在這裡 treap $b$ 的根節點 Heap key 比較小，因此當作根節點，而 treap $a$ 和 treap $b$ 原本的左子樹則要接在 treap $b$ 的左邊。

:::spoiler 決定根節點之後的兩棵 treap {state=open}
:::

而可以發現， treap $a$ 和原本的 treap $b$ 左子樹也需要做 merge 操作，因此就遞迴下去直到兩棵子樹合併完成。

:::spoiler 用 GIF 呈現整個合併過程 {state=open}

藍色部分為當前的 treap $a$ ，綠色部分為 treap $b$ ，黑色是已經合併完成的部分。


:::

寫成程式碼如下

node* merge(node* a,node* b){
    if(!a||!b) return a?:b;  // 邊界處理，如果其中一棵子樹為空則回傳另一邊
    if(a->heap_key<b->heap_key){
        a->r=merge(a->r,b);
        return a;
    }
    b->l=merge(a,b->l);
    return b;
}

#### Split

Split 要做的事情就是將一棵 treap 依照給定的 tree key -- $k$ 切成兩棵 treap : $a,b$。其中 treap $a$ 的 tree key 都小於 $k$ ， treap $b$ 的 tree key 都大於等於 $k$ 。

:::spoiler 這是一棵 treap {state=open}
:::

將這棵 treap 沿著 $k=5$ 來切成兩棵 treap $a,b$

首先先判斷根節點 `8|1` 屬於 $a$ 還是 $b$ ，因為 $8\geq k$ 所以 `8|1` 節點應該屬於 treap $b$ ，而 `8|1` 的右子樹因為 BST 的性質可以確定 tree key 都大於等於 $8$ ，因此也都屬於 treap $b$。

:::spoiler 根節點和其右子樹應屬於 treap b {state=open}

:::

接下來對 `3|3` 這個節點也需要做一樣的事，判斷目前的節點 tree key 比 $k=5$ 大還是小。
最終就可以得到切割好的兩個 treap $a,b$ 。

:::spoiler 用 GIF 呈現整個切割過程 {state=open}

黑色是尚未切割的部分，藍色部分為當前的 treap $a$ ，綠色部分為 treap $b$ 。

:::

寫成程式碼如下

void split(node* cur,int k,node*& a,node*& b){
    if(!cur){a=b=nullptr;return;}  // 邊界處理，如果已經切割完成就結束遞迴
    if(cur->tree_key<k)
        a=cur,split(a->r,k,a->r,b);
    else
        b=cur,split(b->l,k,a,b->l);
}

#### Insert
在一棵 treap $t$ 中加入一個 tree key 為 $k$ 的新節點。

可以發現只要用一個 Split 和兩個 Merge 操作就可以完成。

1. 先將原本的 treap $t$ 按照 $k$ Split 成 treap $a,b$
2. 建一個只有一個節點的 treap $c$， tree key 設成 $k$
3. 將 treap $a,c,b$ 依照這個順序 Merge 起來

就可以得到一棵 treap $t'$ ，為 treap $t$ 加入了新節點後的新 treap。

:::spoiler 用 GIF 呈現整個過程 {state=open}


:::

程式碼如下

node* insert(node* t,int k){
    node *a,*b;
    split(t,k,a,b);
    return merge(merge(a,new node(k)),b);
}

#### erase
在一棵 treap $t$ 中移除 tree key 為 $k$ 的節點。

同理，用 Merge 和 Split 就可以完成，步驟如下：

1. 將 treap $t$ 按照 $k$ Split 成 treap $a,b$ (等於 $k$ 的會在 $b$ 內)
2. 將 treap $b$ 按照 $k+1$ Split 成 treap $c,b$
3. 將 treap $a,b$ Merge 起來

步驟都差不多， GIF 自己腦補

程式碼如下

node* erase(node* t,int k){
    node *a,*b,*c;
    split(t,k,a,b);
    split(b,k+1,c,b);
    return merge(a,b);
}

---

## 用 Treap 解決區間問題

上文的 Treap 基本上只實作了 STL set 中的部分內容，沒有什麼實際用途。但其實可以在每個節點上額外儲存一些訊息，像是**子樹內的值總和**或是**子樹大小**之類的，就可以取代線段樹拿來解決一些像是 RMQ 之類的區間問題。

現在有一個經典的 RMQ 問題 [CSES - Dynamic Range Minimum Queries](https://cses.fi/problemset/task/1649)

> 給定一個長度為 $N$ ，共有 $Q$ 筆操作，每筆操作可能是
> 1. 修改第 $i$ 個位置的值成 $x$
> 2. 求 $[L,R)$ 區間內的最小值
>
> $1\leq N,Q\leq 2\times 10^5$

我們可以建 $N$ 個 tree key 為 $1\sim N$ (或是 $0\sim N-1$ 如果 0-base) 的節點，將 tree key 當成陣列下標，並在每個節點額外儲存陣列的值 $a_i$ 跟子樹內 $a_i$ 的最小值。

程式碼如下

mt19937 mt(hash<string>()(":poop:"));
struct node{
    int p,v,val,mn;  // 為了簡化，p: tree key, v: heap key
    node *l,*r;      // val: a_i, mn: min{a_i}
    node(int x,int y):p(x),v(mt()),val(y),mn(y){
        l=r=nullptr;
    }
    void pull(){  // 等等會用到
        mn=val;
        for(auto i:{l,r})
            if(i) mn=min(mn,i->mn);
    }
};

:::spoiler 示意圖 {state=open}

假設 $N=7$ ，序列為 `3 2 4 5 1 1 5` ，並建出了以下這棵樹

:::

在 Split 和 Merge 操作中因為需要維護子樹內 $a_i$ 的最小值，所以在子樹有修改之後必須多做一個操作: `pull` 。

node* merge(node* a,node* b){
    if(!a||!b) return a?:b;
    if(a->v<b->v){
        a->r=merge(a->r,b);
        a->pull(); 
        return a;
    }
    b->l=merge(a,b->l);
    b->pull();
    return b;
}
void split(node* cur,int k,node*& a,node*& b){
    if(!cur){a=b=nullptr;return;}
    if(cur->p<k)
        a=cur,split(a->r,k,a->r,b),a->pull();
    else
        b=cur,split(b->l,k,a,b->l),b->pull();   
}

修改時直接將要修改的點切出來，修改 `val` 跟 `mn` 就好。
而處理詢問時只要用兩次 Split 將要詢問的區間分割出來，根節點的 `mn` 就是要查詢的答案。

:::spoiler 修改示意圖 {state=open}
假設需要把位置 $4$ 改成 $3$

1. 先 Split $4$ 再 Split $4+1$ 得到三個 treap ，其中中間那個是我們要改的節點
2. 修改節點內的 `val`, `mn`
3. Merge 回去

注意 `pull` 操作的運作和 `mn` 值的改變


:::

---

## 帶懶標 Treap

學會了如何用 treap 解決上面的區間問題之後，現在來看一下這個問題 [CSES - Range Updates and Sums](https://cses.fi/problemset/task/1735)。

> 給定一個長度為 $N$ ，初始皆為 $0$ 的序列，共有 $Q$ 筆操作，每筆操作可能是
> 1. 將 $[L,R)$ 區間內的值修改成 $x$
> 2. 將 $[L,R)$ 區間內的值加上 $x$
> 3. 求 $[L,R)$ 區間的值總和
>
> $1\leq N,Q\leq 2\times 10^5$

之前的修改方法是對單點的，如果對 $[L,R)$ 遍歷對每個點都分別作修改的話，時間複雜度會是 $O(QN\lg N)$ ，基本上必吃 TLE。

那如果我們一次將整個區間 Split 出來有辦法在很短的時間內，例如 $O(1)$ ，計算出修改後子樹會是什麼值嗎？在這個例子中顯然可以，只要邊記錄子樹大小就可以簡單的算出來對於這整棵子樹裡的每一個點設成某個值或加上某個值之後是多少。

那就在這棵子樹的根節點打上一個標記，代表這個節點以下的整棵子樹都需要做某個操作，同時更新那個點的 sum 值就可以不用遞迴那之下的整個子樹了。而這個操作可以證出是 $O(\lg N)$ 的。

因為增值和設值這兩個操作的做法類似，先只討論增值標記的情況。

:::spoiler 操作示意圖 {state=open}

**Merge**

假設要將橘色的範圍 $[2,6)$ 加上 $2$，一樣先將這個範圍 Split 出來，會得到以下三個 treap


接著在要修改的 treap 的根節點打上標記 ( `tag+=2` )


:::

接下來就是需要把三個 treap merge 起來了，但如果直接 merge 起來的話，根節點上會有 +2 的標記但底下的子樹不是全部都需要 +2 。 因此可以發現，在做 Split/Merge 的時候，如果當前節點有懶標記在上面，需要先透過將標記向下推(做 Push 操作)將它處理掉。

void push(){
    if(tag){
        sum+=tag*sz,val+=tag;
        for(auto i:{l,r})
            if(i) i->tag+=tag;
        tag=0;
    }
}

懶標記的本質就是透過這個標記延遲修改的這個操作，只有需要用到的時候才修改，在這裡就是 Split/Merge 有經過的節點才修改。

:::spoiler 接續上面的範例 {state=open}

現在要將左邊兩個子樹合併，首先先將有懶標記的部分往下推，同時更新 `sum` 。


接下來就和平常的操作一樣，遞迴合併起來，只要遇到有懶標記的就往下推。

只要記得做操作前 Push ，做操作後 Pull 就會是好的。

:::spoiler 流程示意圖 {state=open}
:::

:::spoiler 程式碼如下 {state=close}

mt19937 mt(hash<string>()(":poop:"));
struct node{
    int p,v,sz; ll val,sum,inc,set;
    node *l,*r;
    node(int x,ll y):p(x),v(mt()),sz(1),val(y),sum(y),inc(0),set(LINF){
        l=r=nullptr;
    }
    void pull();
    void push();
};
void node::pull(){
    sz=1;
    for(auto i:{l,r})
        if(i) sz+=i->sz;
    sum=val;
    for(auto i:{l,r}){
        if(!i) continue;
        if(i->set!=LINF)
            sum+=i->set*i->sz;
        else
            sum+=i->sum;
        if(i->inc)
            sum+=i->inc*i->sz;
    }
}
void node::push(){
    if(set!=LINF){
        sum=set*sz,val=set;
        for(auto i:{l,r})
            if(i) i->inc=0,i->set=set;
        set=LINF;
    }
    if(inc){
        sum+=inc*sz,val+=inc;
        for(auto i:{l,r})
            if(i) i->inc+=inc;
        inc=0;
    }
}
node* merge(node* a,node* b){
    if(!a||!b) return a?:b; 
    a->push(),b->push();
    if(a->v<b->v)
        return a->r=merge(a->r,b),a->pull(),a;
    return b->l=merge(a,b->l),b->pull(),b;
}
void split(node* cur,int k,node*& a,node*& b){
    if(!cur){a=b=nullptr;return;}
    cur->push();
    if(cur->p<k)
        a=cur,split(a->r,k,a->r,b),a->pull();
    else
        b=cur,split(b->l,k,a,b->l),b->pull();
}
static inline void solve(){
    int n,q;cin>>n>>q;
    node* root=nullptr;
    for(int i=0;i<n;i++){
        ll k;cin>>k;
        root=merge(root,new node(i,k));
    }
    while(q--){
        int op,ql,qr;cin>>op>>ql>>qr,ql--;
        node *l,*m,*r;
        split(root,ql,l,r);
        split(r,qr,m,r);
        switch(op){
        case 1:{ //  increase
            int k;cin>>k,m->inc+=k;
        }break;
        case 2:{
            int k;cin>>k,m->inc=0,m->set=k;
        }break;
        case 3:{
            ll ans=(m->set!=LINF?m->set*m->sz:m->sum);
            cout<<ans+m->inc*m->sz<<endl;
        }break;
        }
        root=merge(merge(l,m),r);
    }
}

:::

要注意的是在處理不只一個懶標的時候，**懶標的順序很重要**。如果先做了懶標 a 再做懶標 b ，那不管在 push 還是 pull 都要使用一樣的順序，且要確保新的懶標疊上去前舊的不會有影響。

---

## Split by size

> 給定一個長度為 $N$ 的序列，共有 $Q$ 筆操作，每筆操作可能是
> 1. 刪掉位於 $i$ 位置的值 (使序列長度 $-1$ )
> 2. 求前面數來 $[L,R)$ 區間內的和
>
> $1\leq N,Q\leq 2\times 10^5$

原本我們把 tree key 當作下標，但這裡的 tree key 會隨著刪掉的操作變化，這樣的話要怎麼解決呢？

有兩種解決辦法，其中一種是再開一個懶標來把刪掉的節點後面的 tree key 都 $-1$ ，但這種方法有點邪教，而且會耗費額外記憶體跟增加實作複雜度，另一種則是需要觀察 tree key 到底在 Merge/Split 中發揮什麼作用。

因為 Merge 中沒有用到 tree key ，所以只需要看 Split 的部分：

void split(node* cur,int k,node*& a,node*& b){
    if(!cur){a=b=nullptr;return;}
    if(cur->p<k)
        a=p,split(a->r,k,a->r,b),a->pull();
    else
        b=p,split(b->l,k,a,b->l),b->pull();
}

可以看到 tree key 的作用只有決定要向左邊分割還是向右邊分割，那其實也可以用其他的節點內的資訊分割吧，像是**子樹大小**之類的，可以將切割條件改成切出前 $k$ 個元素和 $k$ 個元素以後。

inline int size(node* p){return p?p->sz:0;}
void split_by_size(node* cur,int k,node*& a,node*& b){
    if(!cur){a=b=nullptr;return;}
    if(size(cur->l)+1<=k)
        a=p,split(a->r,k-size(cur->l)-1,a->r,b),a->pull();
    else
        b=p,split(b->l,k,a,b->l),b->pull();
}

像這樣就可以不用存 tree key ，只需要維護子樹大小 ( `sz` ) 就可以處理這個問題了。

### 奇怪的區間問題

既然 tree key 已經不需要了，那代表說這種變化型的 treap 其實也不需要遵守 BST 的**左子樹 tree key 比當前點 tree key 小**這種限制了，那就可以作一些奇怪的區間問題，像是 [CSES - Cut and Paste](https://cses.fi/problemset/task/2072)。

> 給定一個長度為 $N$ 的字串，進行 $Q$ 次操作
> 每次將字串 $[L,R)$ 的區間剪下來貼到字串末端
> $1\leq N,Q \leq 2\times 10^5$

因為我們做 split 不再需要 tree key ，而是只需要子樹大小，因此直接 Split 完 Merge 到後面去就好。

---

## 持久化 Treap

接下來看這個問題 [2012 ACM-ICPC Asia Hatyai Regional Programming Contest - pE Version Controlled IDE](https://codeforces.com/gym/101549/problem/E)

> 請你實作一個 IDE ，包含以下操作
> 1. 在目前前面數來第 $p$ 個字元後加入字串 $s$
> 2. 從目前前面數來第 $p$ 個字元起移除 $c$ 個字元
> 3. 輸出第 $v$ 個版本內從前面數來第 $p$ 個字元起的 $c$ 個字元
>
> 每個 1 或 2 操作做完之後都會產生一個新的版本
> 總操作數 $\leq 50,000$，保證過程中最長不會超過 $1,000,000$

可以發現這個題目除了需要保存歷史版本以外都可以用 split by size 的方法來解決，那要怎麼保存歷史版本呢？總不可能每次做完一個操作就直接複製整棵 treap 吧，這樣時空複雜度會變成 $O(QN)$ 。

再看一次 Merge 和 Split 操作，

:::spoiler Merge/Split 示意圖 {state=open}

**Merge**

**Split**
:::

可以發現不管是 Merge 還是 Split ，都只會產生出 $O(\lg N)$ 個與之前值不一樣的節點，旁邊左右子樹至少有一邊是基本上完全沒動到的，那我們可以另外存這些有改變到的節點，而其他節點就沿用之前的就好。

程式碼如下

template<typename T1,typename T2=T1> using P=pair<T1,T2>;
mt19937 mt(hash<string>()(":poop:"));
constexpr int maxn = 7e6;
struct node {
    node *l, *r;
    char c; int v, sz;
    node(char x = '$'): c(x), v(mt()), sz(1) {
        l = r = nullptr;
    }
    node(node* p) {*this = *p;}
    void pull() {
        sz = 1;
        for (auto i : {l, r})
            if (i) sz += i->sz;
    }
} arr[maxn], *ptr = arr;
inline int size(node* p) {return p ? p->sz : 0;}
node* merge(node* a, node* b) {
    if (!a || !b) return a ? : b;
    if (a->v < b->v) {
        node* ret = new(ptr++) node(a);
        ret->r = merge(ret->r, b), ret->pull();
        return ret;
    }
    else {
        node* ret = new(ptr++) node(b);
        ret->l = merge(a, ret->l), ret->pull();
        return ret;
    }
}
P<node*> split(node* p, int k) {
    if (!p) return {nullptr, nullptr};
    if (k >= size(p->l) + 1) {
        auto [a, b] = split(p->r, k - size(p->l) - 1);
        node* ret = new(ptr++) node(p);
        ret->r = a, ret->pull();
        return {ret, b};
    }
    else {
        auto [a, b] = split(p->l, k);
        node* ret = new(ptr++) node(p);
        ret->l = b, ret->pull();
        return {a, ret};
    }
}
int d = 0;
string print(node* p) {
    if (!p) return "";
    string ret = print(p->l);
    ret += p->c, d += (p->c == 'c');
    return ret + print(p->r);
}

## Randomized BST

Merge 時不用 heap key ，而是根據兩邊子樹大小來決定哪一邊要當根。

少一點點空間但因為需要常常取亂數所以常數比較大，基本上對競程完全沒有實用價值先不提。

但有趣的是這樣就變成沒有 heap key 也沒有 tree key 了，嚴格來講這已經只是一棵二元樹，不滿足 BST 的性質也不滿足 Heap 的性質。有興趣的人可以自己研究。