Shocking! I actually wrote fhq Treap#
First %fhq master
Then %zxy master
Node Definition#
struct node
{
int w,siz,rdm;//weight, size (including itself), random number
int l,r;//left and right children
} nd[MAXN];
Special Operations#
fhq Treap, also known as rotationless Treap, maintains the properties of balance and heap by splitting and merging.
Split by Value#
Split the tree into two trees, x and y, where all elements in x are less than or equal to w, and all elements in y are greater than w.
Pass by address, after calling, x and y will be the roots of the new trees.
I initially used pass by pointer, but I was too weak and couldn't get it right.
void splitV(int p,int w,int &x,int &y)//p is the current node being updated
{
if(p==0)//boundary
{
x=y=0;
}
else
{
if(nd[p].w<=w)//current node is smaller than w, so it and its left subtree belong to x
{
x=p;
splitV(nd[p].r,w,nd[p].r,y);//replace x with nd[p].r, so that any node smaller than v in the right subtree can be connected to the right of x
}
else
{
y=p;
splitV(nd[p].l,w,x,nd[p].l);
}
update(p);//update its own size
}
}
Split by Node Count#
As we all know, the result of an inorder traversal of a BST is a sorted sequence (but I didn't think of this at first). So the nodes can be divided into two parts: the first k largest nodes and the remaining nodes.
void splitS(int p,int num,int &x,int &y)
//Separate the first k numbers of the inorder traversal into a separate tree, and the rest into another tree
//The inorder traversal results in nodes arranged in ascending order of size.
//Because the smallest one is visited first. (first left, then middle, then right)
{
if(p==0)
{
x=y=0;
}
else
{
if(nd[nd[p].l].siz>=num)//The left side is larger than the required number
{
y=p;
splitS(nd[p].l,num,x,nd[p].l);//There are nodes smaller than p but larger than the num in its left child.
}
else
{
x=p;
splitS(nd[p].r,num-nd[nd[p].l].siz-1,nd[p].r,y);//The left side is less than num, find the (num-nd[nd[p].l].siz-1)th largest on the right side
}
update(p);//update its own size
}
}
Merge#
Given that all elements in x are less than or equal to all elements in y, merge these two trees and return the new root.
This is where the properties of a heap are reflected.
int merge(int x,int y)
{
if(x==0||y==0)
{
return x+y;//If one of them has a value, that value will be returned
}
else
{
int tmp=0;
if(nd[x].rdm>=nd[y].rdm)//I guess other unequal relationships can be used here
{
//x is the root
tmp=x;
nd[x].r=merge(nd[x].r,y);//Merge the right child with y, and then connect it to the right of x
}
else
{
tmp=y;
nd[y].l=merge(x,nd[y].l);
}
update(tmp);
return tmp;
}
}
Basic Operations of Balanced Trees#
Insertion#
First create a new node
int newNd(int x)
{
++newp;
nd[newp].w=x;
nd[newp].rdm=rand();
nd[newp].siz=1;
return newp;
}
Split by weight, then merge the new node and the two split trees by size
void insert(int w)//
{
int x=0,y=0;
int p=newNd(w);
splitV(root,w,x,y);
x=merge(x,p);
root=merge(x,y);
}
Deletion#
Split by w-1 and w into three trees
The middle tree has all nodes with weight w
Merge its left and right children, discard the root, and delete a node
Remember to merge them back
void remove(int w)
{
int x=0,y=0,z=0;
splitV(root,w,x,y);
splitV(x,w-1,x,z);
z=merge(nd[z].l,nd[z].r);
root=merge(merge(x,z),y); //Merge the left and right subtrees of z to delete a v
}
Find Rank#
Split by value, return the size of the left child plus 1
int rank(int w)
{
int x=0,y=0,ret=0;
splitV(root,w-1,x,y);
ret=nd[x].siz+1;
root=merge(x,y);
return ret;
}
Find kth Largest#
Split by rank...
int kth(int k)
{
int x=0,y=0,z=0;
splitS(root,k,x,y);
splitS(x,k-1,x,z);
int ret=nd[z].w;
root=merge(merge(x,z),y);
return ret;
}
Predecessor#
Split by w-1, find the largest in the smaller tree
int front(int w)
{
int x=0,y=0;
splitV(root,w-1,x,y);
int p=x;
while(nd[p].r)
{
p=nd[p].r;
}
root=merge(x,y);
return nd[p].w;
}
Successor#
Split by w, find the smallest in the larger tree
int back(int w)
{
int x=0,y=0;
splitV(root,w,x,y);
int p=y;
while(nd[p].l)
{
p=nd[p].l;
}
root=merge(x,y);
return nd[p].w;
}
Example Problem: Luogu P3369 Normal Balanced Tree#
Just the six operations mentioned above
Interval Reversal (Lazy Tag)#
Luogu P3835 Artistic Balanced Tree
When reversing, set the lazy tag
void fan(int x,int y)
{
int l,p,r;
split(root,y,l,r);
split(l,x-1,l,p);
nd[p].laz^=1;
root=merge(merge(l,p),r);
}
Handle lazy tags during split, merge, and output
void split(int p,int siz,int &x,int &y)
{
if(p==0)
{
x=y=0;
return;
}
if(nd[p].laz)
{
push_down(p);
}
if(nd[nd[p].l].siz>=siz)
{
y=p;
split(nd[p].l,siz,x,nd[p].l);
}
else
{
x=p;
split(nd[p].r,siz-nd[nd[p].l].siz-1,nd[p].r,y);
}
update(p);
}
int merge(int x,int y)
{
if(x==0||y==0)
{
return x+y;
}
if(nd[x].rdm>nd[y].rdm)
{
if(nd[x].laz)push_down(x);
nd[x].r=merge(nd[x].r,y);
update(x);
return x;
}
else
{
if(nd[y].laz)push_down(y);
nd[y].l=merge(x,nd[y].l);
update(y);
return y;
}
}
void out(int p)
{
if(nd[p].laz)
{
push_down(p);
}
if(nd[p].l)
{
out(nd[p].l);
}
printf("%d ",nd[p].w);
if(nd[p].r)
{
out(nd[p].r);
}
}
Propagation
void push_down(int p)
{
swap(nd[p].l,nd[p].r);
nd[p].laz=0;
nd[nd[p].l].laz^=1;
nd[nd[p].r].laz^=1;
}
Persistent#
Very simple, just add nodes for modification during split and merge, and use the root array to record versions.
However...
I'm going crazy...
Below are the split and merge functions.
void split(int p,int w,int &x,int &y)
{
if(p==0)
{
x=y=0;
}
else
{
int newn=++newp;
nd[newn]=nd[p];
if(nd[p].w<=w)
{
x=newn;
split(nd[x].r,w,nd[x].r,y);
}
else
{
y=newn;
split(nd[y].l,w,x,nd[y].l);
}
update(newn);
}
}
int merge(int x,int y)
{
if(x==0||y==0)
{ return x+y; }
int newn=++newp;
if(nd[x].rdm>nd[y].rdm)
{
nd[newn]=nd[x];
nd[newn].r=merge(nd[newn].r,y);
}
else
{
nd[newn]=nd[y];
nd[newn].l=merge(x,nd[newn].l);
}
update(newn);
return newn;
}