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 attached 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 we can divide the nodes into two parts: the first k largest and the remaining.
void splitS(int p,int num,int &x,int &y)
//Separate the first k numbers obtained by inorder traversal into a separate tree, and the rest into another tree
//The inorder traversal results in nodes arranged in order of size.
//Because the smallest one will be 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 kth 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 smaller 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 property of heap is 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 inequality relations 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 attach 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 Tree#
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 modifications 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;
}