个人主页

推荐博文

Fhq-Treap总结：短小精悍不旋转的神级数据结构

[学习笔记]FHQ-Treap及其可持久化

正文

其实那天本来想在cf里发的，结果发现要英文，英语不好，就咕了……
今天整u盘找出来了QAQ

FHQ-Treap，就是不用旋转的函数式平衡树。（FHQ是范浩强orz）
基本思想：通过对平衡树进行分割（split）和合并（merge）完成维护平衡。
基本操作：插入，删除，查询排名，查询数值，求前驱，求后继

首先Treap，真身为二叉搜索树（BST），即左儿子<父节点<右儿子。为了避免数据毒瘤造成树很长，
导致效率下降，平衡树诞生了。
Splay优良解释
Treap就是给每个结点赋一个random值，在BST的前提下维护random的值的堆性质。
在Splay中最难理解的就是rotate，但是FHQ更加板子，也更好理解，个人比较喜欢。

FHQ-Treap 学习笔记
学军day2 2020.1.19

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int val,rnd,l,r,size;
}tr[1000010];

int merge( int x,int y )		//合并两个Treap（保证x的值小于y） 
{
	if ( !x && !y ) return x+y;
	update( x ); update( y );          //就是根据左右子节点的size更新父节点，这里省略代码了
	if ( tr[x].rnd<tr[x].rnd ) 		//根据random的值，使y成为x的右子树，维护heap性质 
	{	
		tr[x].r=merge( tr[x].r,y );
		update( x ); return x;
	}
	else
	{
		tr[y].l=merge( tr[y].l,x ); 		//使x成为y的左子树 
		update( y ); return y;
	}
}

void split1( int now,int k,int &x,int &y )		//把一个Treap分成两树（按权值分）
{
	if ( now==0 ) 
	{
		x=y=0; return;
	}
	if ( tr[now].val<=k ) x=now,split1( tr[now].r,k,tr[now].r,y );		//now比k小，左子树+根节点→x，递归分割右子树
	else y=now,split1( tr[now].l,k,x,tr[now].l ); 
	update( x ); update( y ); 
} 

void split2( int now,int k,int &x,int &y )		//按size分
{
	update( now );
	if ( k<=tr[tr[now].l].size ) y=now,split2( tr[now].l,k,x,tr[now].l );
	else x=now,split2( tr[now].r,k-tr[tr[now].l].size-1,tr[now].r,y );
} 

void insert( int val )
{
	split1( root,val,x,y );		//先分成两棵树
	root=merge( merge( x,New(val) ),y );		//合并左树和新节点，合并左右两树 
}

void del( int val )
{
	split1( root,val,x,z ); split1( x,val-1,x,y );  	//此时要删除的节点（val）为y的根节点
	y=merge( tr[y].l,tr[y].r ); //去除val的影响
	root=merge( merge( x,y ),z );  
} 

int Get_rank( int val )
{
	split1( root,val-1,x,y ); 
	int answer=tr[x].size;
	merge( x,y );
	return answer;
}

int Get_val( int rk )
{
	while ( 1 )
	{
		if ( k<=tr[tr[now].l].size ) now=tr[now].l;		//k比左树小，左树内部； 
		else
		{
			if ( k==tr[tr[now].l].size+1 ) return now;		//正好为根节点
 			else k-=tr[tr[now].l].size+1,now=tr[now].r;		//在右子树中 
		}
	}
}

前驱：
1.以val-1为界限分割root为x，y
2.在x中Get_val（ tr[x].size ）
3.合并

后继：
1. 以val分割root为x，y
2.在y中Get_val（1）
3.合并

分离区间l—r
1. split2（ root，r，x，y）
2. split2（ x，l-1，a，b ）
3. 最终操作序列为b

题目：POJ3580 SuperMemo