owned this note
owned this note
Published
Linked with GitHub
---
tags: code
---
# Treap (樹堆)
[TOC]
## Introduction
1. `Treap` $=$ `Tree` $+$ `Heap`，
所以要同時維護 `Tree` 性質和 `Heap` 性質，
每個節點存 `key` 和 `pri(priority)`，
`key` 維護 `Tree` 性質，
`pri` 維護 `Heap` 性質。
2. 基本操作期望複雜度 $O(\log n)$。
3. 自平衡樹。
## Node
```cpp=
mt19937 rd; // random
struct node {
node *l, *r;
int key, pri;
node(int k): key(k), pri(rd()) {
l = r = nullptr;
}
} *root = nullptr;
```
## Tree 性質
對於每個節點的，
左子樹所有節點的 `key` 都小於自己的 `key`，
右子樹所有節點的 `key` 都大於等於自己 `key`，
$\to$ Treap is a `Binary Search Tree.`
## Heap 性質
對於所有節點，
滿足子樹的所有 `pri` 都比該節點的 `pri` 大，
$\to$ Treap is a `Heap.`
## Operation
透過 `merge` 和 `split` 來達成二元樹的平衡。
### Merge
```cpp=
node* merge(node* a, node* b) {
if (!a || !b) return a ? : b;
if (a->pri < b->pri) return a->r = merge(a->r, b), a;
else return b->l = merge(a, b->l), b;
}
```
### Split
```cpp=
void split(node* cur, node*& a, node*& b, int k) {
if (!cur) a = b = nullptr;
else if (cur->key < k) a = cur, split(cur->r, a->r, b, k);
else b = cur, split(cur->l, a, b->l, k);
}
```
### Insert
```cpp=
void insert(node*& root, int k) {
node *a, *b;
split(root, a, b, k);
root = merge(a, merge(new node(k), b));
}
```
### Erase
```cpp=
bool erase(node*& cur, int k) {
if (!cur) return 0;
if (cur->key == k) {
node* t = cur;
cur = merge(cur->l, cur->r);
delete t;
return 1;
}
return erase(k < cur->key ? cur->l : cur->r, k);
}
```
### Count
```cpp=
bool count(node* cur, int k) {
if (!cur) return false;
if (cur->key == k) return true;
return count(k < cur->key ? cur->l : cur->r, k);
}
```
### Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
mt19937 rd; // random
struct node {
node *l, *r;
int key, pri;
node(int k): key(k), pri(rd()), l(0), r(0) {}
} *root = nullptr;
node* merge(node* a, node* b) {
if (!a || !b) return a ? : b;
if (a->pri < b->pri) return a->r = merge(a->r, b), a;
else return b->l = merge(a, b->l), b;
}
void split(node* cur, node*& a, node*& b, int k) {
if (!cur) a = b = nullptr;
else if (cur->key < k) a = cur, split(cur->r, a->r, b, k);
else b = cur, split(cur->l, a, b->l, k);
}
void insert(node*& root, int k) {
node *a, *b;
split(root, a, b, k);
root = merge(a, merge(new node(k), b));
}
bool erase(node*& cur, int k) {
if (!cur) return 0;
if (cur->key == k) {
node* t = cur;
cur = merge(cur->l, cur->r);
delete t;
return 1;
}
return erase(k < cur->key ? cur->l : cur->r, k);
}
bool count(node* cur, int k) {
if (!cur) return false;
if (cur->key == k) return true;
return count(k < cur->key ? cur->l : cur->r, k);
}
```
## 名次樹(排名樹)
節點增加一個元素 `size`，
存左子樹的 `size` $+$ 右子樹的 `size` $+$ 1
### Size
- 輔助函數，確保某些情況下 ( `node` 為 `nullptr` 時 ) 仍能正常操作
```cpp=
int size(node* cur) {
return cur ? cur->size : 0;
}
```
### Rank
- 如果同時有插入和查詢 $rank$，可以把兩個操作一起處理，減少常數大小。
```cpp=
int rank(node*& root, int key) {
node *a, *b;
split(root, a, b, key);
int res = a ? a->size : 0;
return root = merge(a, b), res;
}
```
### Problems
:::spoiler `ZJ d788. 排名順序 & d794. 世界排名`
```cpp=
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
mt19937 rd; // random
struct treap {
struct node {
node *l, *r;
int key, pri, size;
void pull() {
size = (l ? l->size : 0) + (r ? r->size : 0) + 1;
}
node(int k): key(k), pri(rd()), size(1), l(0), r(0) {}
} *root;
int size(node* cur) {
return cur ? cur->size : 0;
}
node* merge(node* a, node* b) { // avg. O(log n)
if (!a || !b) return a ? : b;
if (a->pri < b->pri) return a->r = merge(a->r, b), a->pull(), a;
else return b->l = merge(a, b->l), b->pull(), b;
}
void split(node* cur, node*& a, node*& b, int k) { // avg. O(log n)
if (!cur) {a = b = nullptr; return;}
if (cur->key < k) a = cur, split(cur->r, a->r, b, k);
else b = cur, split(cur->l, a, b->l, k);
cur->pull();
}
int insert(node*& root, int k) {
node *a, *b;
split(root, a, b, k);
int res = size(a);
return root = merge(a, merge(new node(k), b)), res;
}
int insert(int k) {return insert(root, k);}
treap(): root(nullptr) {}
};
#define _ ios::sync_with_stdio(false), cin.tie(nullptr);
int main() { _
for (int n, x; cin >> n;) {
treap tree;
for (int i = 1; i <= n; i++)
cin >> x, cout << i - tree.insert(x) << '\n';
}
}
```
:::
## 第 k 小
### size_split
```cpp=
void ssplit(node* cur, node*& a, node*& b, int k) { // size_split
if (!cur) {a = b = nullptr; return;}
if (k >= size(cur->l) + 1) a = cur, ssplit(cur->r, a->r, b, k - (size(cur->l) + 1));
else b = cur, ssplit(cur->l, a, b->l, k);
cur->pull();
}
```
### erase
- 藉由 `size_split` 的概念，可以寫出另一種比較好理解的 `erase`
```cpp=
bool erase(node*& cur, int k) {
node *a, *b, *c;
split(cur, a, b, k);
if (!b) return 0;
ssplit(b, b, c, 1);
if (b->key == k) {
delete b;
return cur = merge(a, c), 1;
}
return cur = merge(a, merge(b, c)), 0;
}
```
### kth
- 藉由 `size_split` 把前 $k$ 個點切出來，再往後切一下，所得即為 `kth`
```cpp=
node* kth(node*& root, int k) {
node *a, *b, *c;
ssplit(root, a, c, k);
ssplit(a, a, b, k - 1);
root = merge(a, merge(b, c));
return b;
}
```
## 區間反轉
Coming.
Google Drive
Gist
Clipboard
Sign in with Wallet
