# data structure treap

Activities - AcWing

Reference - "Advanced Guide to Algorithm Competition" -lyd

I. Overview

2. Detailed operation

1. Common operations

2. Structure definition

3. Operating basic functions

(1)pushup

(2) Get a new node

(3) left-handed right-handed

(4) Establishment

(5) Insertion operation (such as inserting k)

(6) Delete operation

(7) Query operation

practical application

# I. Overview

The binary search tree that satisfies the bst property is not unique. We can balance the size of the left and right subtrees by changing the shape of the binary search tree, so that the depth of the entire tree can be maintained at the logn level.

The change method is divided into "left-handed" and "right-handed". Please refer to the data structure textbook for details.

Treap is a compound word of tree and heap. If the node values ​​are random, then the resulting tree will have an average logn level of depth.

When Treap inserts a new node, it gives the node a random weight. Then, like the insertion process of the binary heap, it is checked from the bottom up, and when a node does not satisfy the property of the large root heap, a single rotation is performed, so that the relationship between the node and its parent node is reversed.

In particular, for the deletion operation, we can directly rotate the deleted node down to a leaf node, and then delete it directly.

In short, Treap maintains the bst property through proper single rotation, and at the same time makes the additional weights randomly generated on the node satisfy the large root heap property. All operations are logN level.

## 2. Structure definition

```int n;
struct Node{
int l,r;
int key,val;
int cnt,size;
}tr[N];

int root,idx;```

l, r represent the numbers of the left and right child nodes. key represents the value of the node, and val represents the random weight. cnt indicates how many times the current key appears, and size indicates how many nodes there are in the entire subtree.

Both cnt and size are established to satisfy the two operations of ranking evaluation and ranking based on value

### (1)pushup

Calculate size based on child nodes. For 3 4 operations

```void pushup(int p)
{
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}```

### (2) Get a new node

```int get_node(int key)
{
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].cnt=tr[idx].size=1;
return idx;
}```

### (3) left-handed right-handed

note quotes

```void zig(int &p)//Right-handed
{
int q=tr[p].l;
tr[p].l=tr[q].r,tr[q].r=p,p=q;
pushup(tr[p].r),pushup(p);
}

void zag(int &p)
{
int q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;
pushup(tr[p].l),pushup(p);
}```

### (4) Establishment

Set up two sentries. Don't reverse the order of sentries.

```void build()
{
get_node(-INF),get_node(INF);
root=1,tr[root].r=2;
pushup(root);

if(tr[1].val<tr[2].val) zag(root);
}```

### (5) Insertion operation (such as inserting k)

If p is empty, create a new node.

If the current key==k, then the node cnt++

If it is greater than k, insert it in the left subtree, and rotate right as needed when backtracking

If it is less than k, insert in the right subtree, and rotate left as needed when backtracking

Finally, for each node, since the insertion changes the subtree information, the current node must be pushed up

```void insert(int &p,int key)
{
if(!p) p=get_node(key);
else if(tr[p].key==key) tr[p].cnt++;
else if(tr[p].key>key)
{
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[tr[p].r].val) zig(p);
}
else
{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[tr[p].l].val) zag(p);
}
pushup(p);
}```

### (6) Delete operation

If the node is empty, it is meaningless and return s directly

If the current node key==k:

If cnt>1, just cnt--

If not a leaf node:

If there is no right subtree, or right rotation is required: right rotation, and then recursively delete on the right subtree of p

Correspondingly, if there is no left subtree or left rotation is required: just left rotation, and then recurse the left subtree

The remaining cases are leaf nodes: just p=0 and delete

If the current node key>k recursive left subtree

else recursive right subtree

Finally, you still need to remember to pushup! ! ! !

```void remove(int &p,int key)
{
if(!p) return;
if(tr[p].key==key)
{
if(tr[p].cnt>1) tr[p].cnt--;
else if(tr[p].l||tr[p].r)
{
if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r,key);
}
else
{
zag(p);
remove(tr[p].l,key);
}
}
else p=0;
}
else if(tr[p].key>key) remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}```

### (7) Query operation

```int get_rank_by_key(int p,int key)
{
if(!p) return 0;
if(tr[p].key==key) return tr[tr[p].l].size+1;
if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);
return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}

int get_key_by_rank(int p,int rank)
{
if(!p) return INF;
if(tr[tr[p].l].size>=rank) return get_key_by_rank(tr[p].l,rank);
if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].key;
return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}

int get_prev(int p,int key)
{
if(!p) return -INF;
if(tr[p].key>=key) return get_prev(tr[p].l,key);
return max(tr[p].key,get_prev(tr[p].r,key));

}
int get_next(int p, int key)    // Find the smallest number that is strictly greater than key
{
if (!p) return INF;
if (tr[p].key <= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}
```

Full code:

```#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N =1e5+10,INF=1e8;

int n;
struct Node{
int l,r;
int key,val;
int cnt,size;
}tr[N];

int root,idx;

void pushup(int p)
{
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}

int get_node(int key)
{
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].cnt=tr[idx].size=1;
return idx;
}

void zig(int &p)//Right-handed
{
int q=tr[p].l;
tr[p].l=tr[q].r,tr[q].r=p,p=q;
pushup(tr[p].r),pushup(p);
}

void zag(int &p)
{
int q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;
pushup(tr[p].l),pushup(p);
}

void build()
{
get_node(-INF),get_node(INF);
root=1,tr[root].r=2;
pushup(root);

if(tr[1].val<tr[2].val) zag(root);
}

void insert(int &p,int key)
{
if(!p) p=get_node(key);
else if(tr[p].key==key) tr[p].cnt++;
else if(tr[p].key>key)
{
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[tr[p].r].val) zig(p);
}
else
{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[tr[p].l].val) zag(p);
}
pushup(p);
}

void remove(int &p,int key)
{
if(!p) return;
if(tr[p].key==key)
{
if(tr[p].cnt>1) tr[p].cnt--;
else if(tr[p].l||tr[p].r)
{
if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r,key);
}
else
{
zag(p);
remove(tr[p].l,key);
}
}
else p=0;
}
else if(tr[p].key>key) remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}

int get_rank_by_key(int p,int key)
{
if(!p) return 0;
if(tr[p].key==key) return tr[tr[p].l].size+1;
if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);
return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}

int get_key_by_rank(int p,int rank)
{
if(!p) return INF;
if(tr[tr[p].l].size>=rank) return get_key_by_rank(tr[p].l,rank);
if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].key;
return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}

int get_prev(int p,int key)
{
if(!p) return -INF;
if(tr[p].key>=key) return get_prev(tr[p].l,key);
return max(tr[p].key,get_prev(tr[p].r,key));

}
int get_next(int p, int key)    // Find the smallest number that is strictly greater than key
{
if (!p) return INF;
if (tr[p].key <= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}

int main()
{
build();
cin>>n;
while(n--)
{
int op,x;
cin>>op>>x;
if(op==1)   insert(root,x);
else if(op==2)  remove(root,x);
else if(op==3)  cout<<get_rank_by_key(root,x)-1<<endl;
else if(op==4)  cout<<get_key_by_rank(root,x+1)<<endl;
else if(op==5)  cout<<get_prev(root,x)<<endl;
else
{
cout<<get_next(root,x)<<endl;
}
}

return 0;
}```

## practical application

```#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int N =33010,INF=1e8;
typedef long long LL;

int n;
struct Node{
int l,r;
int key,val;
}tr[N];

int root,idx;

int get_node(int key)
{
tr[++idx].key=key;
tr[idx].val=rand();
return idx;
}

void zig(int &p)
{
int q=tr[p].l;
tr[p].l=tr[q].r,tr[q].r=p,p=q;
}

void zag(int &p)
{
int q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;

}

void build()
{
get_node(-INF),get_node(INF);
root=1,tr[root].r=2;
//if(tr[root].val<tr[tr[root].r].val) zag(root);
}

void insert(int &p,int key)
{
if(!p) p=get_node(key);
else if(tr[p].key==key) return;
else if(tr[p].key>key)
{
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[p].val) zig(p);
}
else
{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[p].val) zag(p);
}

}

int get_prev(int p,int key)
{
if(!p) return -INF;
if(tr[p].key>key) return get_prev(tr[p].l,key);
return max(tr[p].key,get_prev(tr[p].r,key));
}

int get_next(int p,int key)
{
if(!p) return INF;
if(tr[p].key<key) return get_next(tr[p].r,key);
return min(tr[p].key,get_next(tr[p].l,key));
}

int main()
{
build();
cin>>n;

LL res=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(i==1) res+=x;
else res+= min(x - get_prev(root,x),get_next(root,x)-x);
insert(root,x);
}
cout<<res;
return 0;
}

author: yankai