---
# System prepended metadata

title: Treap (fhq)
tags: [algorithm]

---

---
tags: algorithm
---

# Treap (fhq)
---
## 原理
在維持`heap`的同時，做出`平衡二元樹`的操作
:::spoiler heap
:::info
父親的值恆小於(或大於)等於孩子的值 
:::
:::spoiler 問題
:::info
Q:二元樹不是右節點的值要大於節點的值??
A:所以另增另外一個值`pri`來保持`heap`的值
:::

---

## 節點
```cpp=
mt19937 rd;
struct node {
        node *l, *r;
        int pri,val;
        node(int k) : pri(rd()), val(k), sz(1) {l = r = nullptr;}
}
```
---

$$每一個$$
```graphviz
digraph main {
    1[label ="node"]
}
```


$$都視為一個treap$$
<p hidden>

</p>

---
## 主要操作
### merge

- `merge(node *a ,node *b)`
$\implies$ 將兩個`node`，`a`,`b`合併。
:::danger
先決條件: `b` 的每一個元素皆大於等於`a`
:::
複雜度$O(\log N)$

### spilt
- `spilt(node *cur, int k, node *& a, node *& b)` 
 $\implies$ 將`cur`中值小於`k`的節點存到`a`, 大於等於`k`的則存到`b`。
 :::danger
 因為要存下節點，所以`a`, `b`要加參照
 :::
複雜度$O(\log N)$

```graphviz
digraph main {
    treap -> {"<k", ">=k"}[label = spilt]
    {"<k", ">=k"} -> "new treap"[label = merge]
}
```




```cpp=
node* t_merge(node *a, node *b) { //b ele > a ele, and maxium heap
        if(!a || !b) return (a ? a : b);
        if(a -> pri > b -> pri)
            return a -> r = t_merge(a -> r, b),a -> pull(), a;
        else
            return b -> l = t_merge(a, b -> l), b -> pull(), b;
    }

    
    void spilt(node *cur, node *& a, node *& b, int k) { //a ele < k, b ele >= k
        if(!cur) {a = b = NULL; return;}
        if(cur -> val < k) {
            a = cur;
            spilt(cur -> r, a -> r, b, k);
        }
        else {
            b = cur;
            spilt(cur -> l, a, b -> l, k);
        }
    }
```


---
## 基礎操作
### insert
- `insert(int k)`
#### 想法: 先把`treap`一分為二(< k 跟 >= k)，在把node(k)`merge`回去即可

```graphviz
digraph main{
    1[label = ">=k"]
    
    "cur" -> "<k"[label = spilt]
    "cur" -> ">=k"[label = spilt]
    {">=k", "k"} -> 1[label = merge];
    {"<k", 1} -> "new treap"[label = merge]
    {rank = same; "<k", ">=k"}
}
```


``` cpp =
void t_insert(node *&cur, int k) {
        node *a, *b;
        a = b = NULL;
        spilt(cur, a, b, k);
        cur = t_merge(a, t_merge(new node(k), b));
    }
    void t_insert(int k) {t_insert(root, k);}
```


### earse
- `earse(int k)`
#### 想法: 把`treap`一分為二, 把(>=k)的部分在分一次(==k 跟 > k)，把(<k)跟(>k)的merge起來即可
```graphviz
digraph main {
    1[label = cur]
    2[label = "< k"]
    3[label = " >= k"]
    4[label = "== k"]
    5[label = ">k"]
    6[label = "treap with out k"]
    1 -> {2, 3}[label = spilt];
    3 -> {4,5}[label = spilt]
    {2, 5} -> 6[label = merge]
    {rank = same; 2, 3}
}
```

--- 

## 特別的操作

### sspilt
-`sspilt(node *cur, int k, node *a, node *b)`
$\implies$ 將`cur`一分為二，`size(a) = k`, `size(b) = size(cur) - k`

```graphviz
digraph {
    a[label = "size N"]
    a -> "size < k", "size >= k"[label = ssplit]
    "size < k", "size >= k" -> "size N"[label = merge]
}
```
不過這樣就要維護子節點的`size`，要再多存一些值。

```cpp=
mt19937 rd;
struct node {
        node *l, *r;
        int pri,val, sz;
        node(int k) : pri(rd()), val(k), sz(1) {l = r = nullptr;}
        void pull() {sz = (l ? l -> sz :0) + (r ? r -> sz : 0)+ 1;}
}
```

```cpp=
 int cc_sz(node* cur) {return (cur ? cur -> sz : 0);}
void sspilt(node *cur, node *& a, node *& b, int sz) { // a.sz = sz, b.sz else
        if(!cur) {a = b = NULL; return;}
        if(cc_sz(cur -> l) + 1 <= sz) {
            a = cur;
            sz -= cc_sz(cur -> l) + 1;
            sspilt(cur -> r, a -> r, b, sz);
            a -> pull();
        }
        else {
            b = cur;
            sspilt(cur -> l, a, b -> l, sz);
            b -> pull();
        }
    }
```

### 序列第k小
```cpp=
 int k_th(node *& cur, int rnk) {
        node *a, *b, *c;
        a = b = c = NULL;
        sspilt(cur, a, b ,rnk);
        sspilt(a, d, c, rnk - 1);
        int ans = c -> val;
        cur = t_merge(t_merge(d, c), b);
        return ans;
    }
    int k_th(int rnk) {return k_th(root, rnk);}
```

## 實作注意:
- 節點的`size`是左子樹加右子樹在加1
- 用`int size(node *cur)`來確認節點的`size`，以免取到`nullptr`
- 在`spilt`和`sspilt`時，當節點`cur`為`nullptr`時記得把`a, b`設成`nullptr`
- 如果有`spilt`或`sspilt`記得把節點`merge`回去


## 延伸應用 

平衡二元樹還有另一個神奇的作用，可以做線段操作!!!
而且直覺了許多，你可以把`treap`當成一個序列，把id當成搜尋的對象的話，你就可以用`split`來去分割這個序列。
```cpp=
struct node {
    node *l, *r;
    int id, val, pri, sum;
    node(int k) : val(k), pri(rd()), sz(1), sum(k) {l = r = NULL};
    void pull() {sum = (l ? l -> sum : 0) +　(r ? r -> sum : 0) + val;}
};
```

### 區間和
如果你要求`[l, r]`區間和的話只要把`treap`分成三份
```graphviz
digraph {
    "[1, N]" -> "[1, L\-1]", "[L, N]"
    "[L, N]" -> "[L, R]", "[R-1, N]"
}
```
最後在合併起來就好了

### 單點修改
就分出一個節點在`merge`回去就可以了。
### 區間修改
加上懶標記
### 區間翻轉
一樣是懶標記，遇到懶標記時把左右子樹交換即可。







```cpp=
mt19937 rd;
struct treap {
    struct node {
        node *l, *r;
        int val, pri;
        int sz;
        node(int k) : val(k), pri(rd()), sz(1) {l = r = nullptr;}
        void pull() {sz = (l ? l -> sz : 0) + (r ? r -> sz : 0) + 1;}
    }*root = NULL;

    int cc_sz(node* cur) {return (cur ? cur -> sz : 0);}
    node* t_merge(node *a, node *b) { //b ele > a ele, and maxium heap
        if(!a || !b) return (a ? a : b);
        if(a -> pri > b -> pri)
            return a -> r = t_merge(a -> r, b),a -> pull(), a;
        else
            return b -> l = t_merge(a, b -> l), b -> pull(), b;
    }

    void spilt(node *cur, node *& a, node *& b, int k) { //a ele < k, b ele >= k
        if(!cur) {a = b = NULL; return;}
        if(cur -> val < k) {
            a = cur;
            spilt(cur -> r, a -> r, b, k);
            a -> pull();
        }
        else {
            b = cur;
            spilt(cur -> l, a, b -> l, k);
            b -> pull();
        }
    }
    void sspilt(node *cur, node *& a, node *& b, int sz) { // a.sz = sz, b.sz else
        if(!cur) {a = b = NULL; return;}
        if(cc_sz(cur -> l) + 1 <= sz) {
            a = cur;
            sz -= cc_sz(cur -> l) + 1;
            sspilt(cur -> r, a -> r, b, sz);
            a -> pull();
        }
        else {
            b = cur;
            sspilt(cur -> l, a, b -> l, sz);
            b -> pull();
        }
    }

    int k_th(node *& cur, int rnk) {
        node *a, *b, *c, *d;
        a = b = c = NULL;
        sspilt(cur, a, b ,rnk);
        sspilt(a, d, c, rnk - 1);
        int ans = c -> val;
        cur = t_merge(t_merge(d, c), b);
        return ans;
    }
    int k_th(int rnk) {return k_th(root, rnk);}
    
    void t_insert(node *&cur, int k) {
        node *a, *b;
        a = b = NULL;
        spilt(cur, a, b, k);
        cur = t_merge(t_merge(a, new node(k)), b);
    }
    void t_insert(int k) {t_insert(root, k);}

    void t_print(node *cur) {
        if(!cur)return;
        t_print(cur -> l);
        de(cur -> val, cur -> sz);
        t_print(cur -> r);
    }
    void t_print() {t_print(root);}
};
```

