---
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);}
};
```
Sign in with Wallet
Connect another wallet