preface

You don't need to learn tree first!

introduce

Example:( Luogu P3369 [template] common balance tree)

You need to write a data structure to maintain some numbers, which needs to provide the following operations:
1. Insert x x x number
2. Delete x x Number of x (if there are multiple identical numbers, only one will be deleted)
3. Query x x Ranking of x number (ranking is defined as the number of numbers smaller than the current number) + 1 +1 +1 )
4. Query ranking is x x Number of x
5. Request x x Precursor of x (defined as less than x x x. And the maximum number)
6. Request x x Successor of x (successor defined as greater than) x x x. And the smallest number)

General balance trees have annoying rotation operations, which are difficult to write and adjust. So, is there any balance tree that doesn't need to rotate?

That is the irrotational Treap, which is also called fhq Treap because it was invented by fhq.

What are the benefits of it?

1, No rotation
2, The code is short, easy to write and easy to tune
3, High efficiency
4, Support for persistence

fhq Treap

Compared with the balanced tree such as spiral tree and Splay, its operation is very simple, and there are only two core operations: s p l i t split split and m e r g e merge merge.

node

For each node, we need to store the following information:

int ch[2];//Left and right son
int val;//value
int pri;//Random priority
int size;//Subtree size

Everything else is easy to understand. What is this random priority? Leave this doubt for a moment and continue to look down

Basic operation

void maintain(int x)//Maintain node information
{
	t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;//It should be noted that, unlike Splay, fhq Treap only stores one value per node, so it only needs + 1
}//In other words, multiple nodes may store the same value
int new_node(int x)//Create a new node. For convenience, it is packaged as an independent function here
{
	t[++tot].size=1;
	t[tot].val=x;
	t[tot].pri=rand();//Random priority
	return tot;
}

The original random priority is really random! Please continue to look down

division

For a tree (subtree), we should base it on k k k splitting means that the value should be less than or equal to k k The node of k is divided into a tree with a value greater than k k k is divided into another tree. For convenience, we call the first tree A tree and the second tree B tree.

When we according to k k k when splitting a tree (subtree), there are the following situations:

1. The value of the root is less than or equal to k k k. At this time, all the left subtrees are less than or equal to k k k. Right subtree is not necessarily. Therefore, the left subtree and root must belong to A tree, and the right subtree may belong to A tree and B tree. At this time, we take the root of the current tree as the root of tree A, and then according to k k k split right subtree.
2. The value of the root is greater than k k k. Similarly, take the root of the current tree as the root of B tree, and then k k k splits the left subtree.

void split(int cur,int k,int &x,int &y)//x and y are address calls. x represents the root of A tree and Y represents the root of B tree
{
	if(!cur)//It's over
		x=y=0;
	else
	{
		if(t[cur].val<=k)
		{
			x=cur;
			split(t[cur].ch[1],k,t[cur].ch[1],y);
		}
		else
		{
			y=cur;
			split(t[cur].ch[0],k,x,t[cur].ch[0]);
		}
		maintain(cur);//By the way
	}
}

merge

Is to combine two trees into one, but still meet the nature of balanced tree.

We still call the small one A tree and the large one B tree. We can be sure that the values on the A tree are less than those on the B tree, so we have two choices. Either merge tree A into the left subtree of tree B, or merge tree B into the right subtree of tree A. How should we decide?

In addition, we should also note that we should not only maintain the nature of BST, but also maintain the unique nature of balance tree: balance.

Have you made up your mind? The answer is

Random decision!

Since it is necessary to maintain the balance, that is, to make the whole tree tend to be random, random merging is naturally the best choice ω Q.

Then we need to use our random priority. See code:

int merge(int x,int y)//The return value is the root of the merged tree
{
	if(!x||!y)//If one of them is empty, the other is returned directly
		return x+y;
	if(t[x].pri<t[y].pri)//Random priority determines the merging method
	{
		t[x].ch[1]=merge(t[x].ch[1],y);//Merge B tree into the right subtree of A tree
		maintain(x);
		return x;
	}
	else
	{
		t[y].ch[0]=merge(x,t[y].ch[0]);//Merge A tree into the left subtree of B tree
		maintain(y);
		return y;
	}
}

In this way, we have completed the two core operations. Now we're going to use them!

insert

Unlike the rotating balance tree, as long as you master the operations of splitting and merging, the rest is very simple.

Please insert a number k k k how many steps do you need? Just three steps:

Step 1: tear the tree apart.

Step 2: put k k k put it in.

Step 3: merge the trees.

void insert(int k)
{
	int x,y;//Used to store the two split roots
	split(root,k,x,y);//Split according to k
	root=merge(merge(x,new_node(k)),y);//Merge A tree with k, and then merge the merged tree with B tree
}

delete

This is a little more troublesome - one more step:

Step 1: set less than or equal to k k Pull out the tree of k

Step 2: from less than or equal to k k k in the tree k k k's pull out

Step 3: set equal to k k The roots of k's tree are squeezed out

Part IV: less than k k k equals k k k, greater than k k Stick all of k back

A little hard to understand? As an analogy, you now have a note:

There are two red dots on the top:

You want to cut off a red dot. What should you do?

First cut off the right side of the red dot:

Then cut off the left side:

Cut off one red dot:

Glue the left and right:

It seems very retarded

void del(int k)
{
	int x,y,z;//x stores less than k, y stores equal to K, and z stores greater than k
	split(root,k,x,z);//According to K splitting, x is less than or equal to K and z is greater than k
	split(x,k-1,x,y);//Split x according to k-1, X is less than k, and y is equal to K
	y=merge(t[y].ch[0],t[y].ch[1]);//Merge the left and right subtrees of y and squeeze out the roots
	root=merge(merge(x,y),z);//close
}

Query ranking

This is simple, according to k − 1 k-1 k − 1 splitting, A tree s i z e size size is less than k k The number of k, the ranking is s i z e + 1 size+1 size+1.

int rnk(int k)
{
	int x,y,ans;
	split(root,k-1,x,y);//Split according to k-1
	ans=t[x].size+1;
	root=merge(x,y);
	return ans;
}

query value

Sorry, fhq tree has no special method for this, so this operation is the same as other balance trees.

int kth(int cur,int k)
{
	while(1)
	{
		if(k<=t[t[cur].ch[0]].size)
			cur=t[cur].ch[0];
		else
		{
			k-=t[t[cur].ch[0]].size+1;
			if(k<=0)
				return cur;
			cur=t[cur].ch[1];
		}
	}
}

Precursors and successors

The query precursor only needs to be based on k − 1 k-1 Split k − 1, and then find the maximum value in A tree (that is, the query ranking in A tree is s i z e size size).

int pre(int k)
{
	int x,y,ans;
	split(root,k-1,x,y);
	ans=t[kth(x,t[x].size)].val;
	root=merge(x,y);
	return ans;
}

Similarly, for subsequent query, according to k k k split, and then find the minimum value in the B tree (that is, the query ranking in the B tree is 1 1 1).

int nxt(int k)
{
	int x,y,ans;
	split(root,k,x,y);
	ans=t[kth(y,1)].val;
	root=merge(x,y);
	return ans;
}

summary

In fact, as long as you master division and merger, others will be very violent

matters needing attention:

1. When splitting and merging, pay attention to maintaining node information
2. Don't write hi when splitting. Forget to merge back
3. Write down the priority to find the pot of division and merger

code

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#define MAXN 100010
using namespace std;
struct fhq_Treap
{
	int ch[2];
	int val;
	int pri;
	int size;
}
t[MAXN];
int tot,root;
int new_node(int x)
{
	t[++tot].size=1;
	t[tot].val=x;
	t[tot].pri=rand();
	return tot;
}
void maintain(int x)
{
	t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;
}
void split(int cur,int k,int &x,int &y)
{
	if(!cur)
		x=y=0;
	else
	{
		if(t[cur].val<=k)
		{
			x=cur;
			split(t[cur].ch[1],k,t[cur].ch[1],y);
		}
		else
		{
			y=cur;
			split(t[cur].ch[0],k,x,t[cur].ch[0]);
		}
		maintain(cur);
	}
}
int merge(int x,int y)
{
	if(!x||!y)
		return x+y;
	if(t[x].pri<t[y].pri)
	{
		t[x].ch[1]=merge(t[x].ch[1],y);
		maintain(x);
		return x;
	}
	else
	{
		t[y].ch[0]=merge(x,t[y].ch[0]);
		maintain(y);
		return y;
	}
}
void insert(int k)
{
	int x,y;
	split(root,k,x,y);
	root=merge(merge(x,new_node(k)),y);
}
void del(int k)
{
	int x,y,z;
	split(root,k,x,z);
	split(x,k-1,x,y);
	y=merge(t[y].ch[0],t[y].ch[1]);
	root=merge(merge(x,y),z);
}
int rnk(int k)
{
	int x,y,ans;
	split(root,k-1,x,y);
	ans=t[x].size+1;
	root=merge(x,y);
	return ans;
}
int kth(int cur,int k)
{
	while(1)
	{
		if(k<=t[t[cur].ch[0]].size)
			cur=t[cur].ch[0];
		else
		{
			k-=t[t[cur].ch[0]].size+1;
			if(k<=0)
				return cur;
			cur=t[cur].ch[1];
		}
	}
}
int pre(int k)
{
	int x,y,ans;
	split(root,k-1,x,y);
	ans=t[kth(x,t[x].size)].val;
	root=merge(x,y);
	return ans;
}
int nxt(int k)
{
	int x,y,ans;
	split(root,k,x,y);
	ans=t[kth(y,1)].val;
	root=merge(x,y);
	return ans;
}
int n,op,x;
int main()
{
	srand(time(0));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&op,&x);
		if(op==1)
			insert(x);
		else if(op==2)
			del(x);
		else if(op==3)
			printf("%d\n",rnk(x));
		else if(op==4)
			printf("%d\n",t[kth(root,x)].val);
		else if(op==5)
			printf("%d\n",pre(x));
		else
			printf("%d\n",nxt(x));
	}
	return 0;
}