Treap小结

2024-06-16 01:38
文章标签 小结 treap

本文主要是介绍Treap小结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Treap(Tree+Heap)---是一种通过 rand() 来随机生成数字作为修正值来调整的平衡树。

基本操作：

1.旋转。

2.插入（合并重复的），删除（懒惰删除）。

3.查最值，求第k小，求排名。

4.中序遍历就是从小到大的。

5.维护附加关键字.

1.求第k小:

POJ1442

//12321199		1442	Accepted	976K	204MS	C++	2080B	2013-11-22 20:33:35静态
//12321216		1442	Accepted	1804K	329MS	C++	2125B	2013-11-22 20:39:40动态
#include <iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAX 30005
int a[MAX];
int u[MAX];
int tot;
class Node
{
public:int vol,fix;int size;Node *left;Node *right;int lsize(){return left?left->size:0;}int rsize(){return right?right->size:0;}
}*root;//space[MAX]
void left_rotate(Node *&a)
{Node *b=a->right;a->right=b->left;b->left=a;a=b;b=a->left;b->size=b->lsize()+b->rsize()+1;a->size=a->lsize()+a->rsize()+1;
}
void right_rotate(Node *&a)
{Node *b=a->left;a->left=b->right;b->right=a;a=b;b=a->right;b->size=b->lsize()+b->rsize()+1;a->size=a->lsize()+a->rsize()+1;
}
void insert(Node*&p,int vol)
{if(!p){p=new Node();//p=&space[tot++];  //静态p->fix=rand();p->vol=vol;p->size=1;}else if(vol<=p->vol){insert(p->left,vol);p->size++;if(p->left->fix < p->fix)right_rotate(p);}else{insert(p->right,vol);p->size++;if(p->right->fix < p->fix)left_rotate(p);}
}
int get_kth(Node *&p,int k)
{int key=p->lsize()+1;if(k < key)return get_kth(p->left,k);else if(k > key)return get_kth(p->right,k-key);elsereturn p->vol;
}
void init()
{root=NULL;//memset(space,0,sizeof(space));静态//tot=1;
}
int main()
{srand(time(0));int n,m;while(~scanf("%d%d",&m,&n)){for(int i=1;i<=m;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) scanf("%d",&u[i]);int j=1;init();for(int i=1;i<=m;i++){insert(root,a[i]);while(j<=n&&i==u[j]){printf("%d\n",get_kth(root,j));j++;}if(j>n) break;}}return 0;
}

2.动态求最值 

//12321728		3481	Accepted	212K	282MS	C++	1857B	2013-11-22 22:26:19动态
#include <iostream>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<cstring>
using namespace std;
//#define MAX 10000005
class Node
{
public:int vol,fix,cus;Node* left;Node* right;
}*root;//,space[MAX]  
int tot=1;
void r_rotate(Node*&a)
{Node*b=a->left;a->left=b->right;b->right=a;a=b;b=a->right;
}
void l_rotate(Node*&a)
{Node*b=a->right;a->right=b->left;b->left=a;a=b;b=a->left;
}
void insert(Node*&p,int cus,int vol)
{if(!p){p=new Node();//p=&space[tot++];p->fix=rand();p->vol=vol;p->cus=cus;}else if(p->vol >= vol){insert(p->left,cus,vol);if(p->left->fix < p->fix)r_rotate(p);}else{insert(p->right,cus,vol);if(p->right->fix < p->fix)l_rotate(p);}
}
int Min(Node*&p)
{if(!p)return 0;if(!p->left){Node*t=p;int ans=p->cus;p=p->right;delete t;return ans;}else return Min(p->left);
}
int Max(Node*&p)
{if(!p)return 0;if(!p->right){Node*t=p;int ans=p->cus;p=p->left;delete t;return ans;}else return Max(p->right);
}
int main()
{srand(time(0));int a;while(~scanf("%d",&a)&&a){if(a==1){int b,c;scanf("%d%d",&b,&c);insert(root,b,c);}else if(a==3){printf("%d\n",Min(root));}else{printf("%d\n",Max(root));}}return 0;
}

3.区间第k小: 

//12329808		2761	Accepted	3500K	1844MS	C++	3889B	2013-11-25 21:28:45静态
//12329836		2761	Accepted	3900K	3922MS	C++	3962B	2013-11-25 21:34:10动态
#include <iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 2000005
int dog[MAX];
int ans[MAX];
class Interval
{
public:int s,e,k;int id;bool operator<(const Interval a) const{return s<a.s;}
}qu[MAX];
class Node
{
public:int vol,fix,size;Node*left;Node*right;int lsize(){return left?left->size:0;}int rsize(){return right?right->size:0;}
}*root,space[MAX];
int tot;
void r_rotate(Node*&a)
{Node*b=a->left;a->left=b->right;b->right=a;a=b;b=a->right;b->size=b->lsize()+b->rsize()+1;/**RE在这里，不要把求size顺序搞反了*/a->size=a->lsize()+a->rsize()+1;}
void l_rotate(Node*&a)
{Node*b=a->right;a->right=b->left;b->left=a;a=b;b=a->left;b->size=b->lsize()+b->rsize()+1;a->size=a->lsize()+a->rsize()+1;}
void insert(Node*&p,int vol)
{if(!p){p=&space[tot++];//p=new Node();p->left=NULL;p->right=NULL;p->fix=rand();p->vol=vol;p->size=1;}else if(p->vol > vol){p->size++;insert(p->left,vol);if(p->left->fix < p->fix)r_rotate(p);}else{p->size++;insert(p->right,vol);if(p->right->fix < p->fix)l_rotate(p);}
}
void del(Node*&p,int key)
{if(!p) return ;p->size--;  /**注意size的减减**/if(key==p->vol){if(!p->left || !p->right){//Node *t=p;if(!p->left)p=p->right;elsep=p->left;//delete t;}else{if(p->right->fix < p->left->fix){l_rotate(p);p->size--;/**注意size的减减**/del(p->left,key);}else{r_rotate(p);p->size--;/**注意size的减减**/del(p->right,key);}}}else if(key < p->vol)del(p->left,key);elsedel(p->right,key);
}
int find_kth(Node*&p,int k)
{int sum=p->lsize()+1;if(k < sum){return find_kth(p->left,k);}else if(k>sum){return find_kth(p->right,k-sum);}else{return p->vol;}
}
int solve(Interval t1,Interval t2)
{for(int i=t1.s;i<=min(t2.s-1,t1.e);i++)del(root,dog[i]);if(t1.e > t2.e){for(int i=t2.e+1;i<=t1.e;i++)del(root,dog[i]);}for(int i=max(t1.e+1,t2.s);i<=t2.e;i++)insert(root,dog[i]);return find_kth(root,t2.k);
}
int main()
{srand(time(0));//int T;//scanf("%d",&T);int n,m;while(~scanf("%d%d",&n,&m)){root=NULL;tot=1;memset(space,NULL,sizeof(space));for(int i=1;i<=n;i++)scanf("%d",&dog[i]);for(int i=1;i<=m;i++){scanf("%d%d%d",&qu[i].s,&qu[i].e,&qu[i].k);if(qu[i].s > qu[i].e) swap(qu[i].s,qu[i].e);qu[i].id=i;}sort(qu+1,qu+1+m);for(int i=qu[1].s;i<=qu[1].e;i++)insert(root,dog[i]);ans[qu[1].id]=find_kth(root,qu[1].k);for(int i=2;i<=m;i++){ans[qu[i].id]=solve(qu[i-1],qu[i]);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);}return 0;
}




这篇关于Treap小结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1065160。

相关文章

分布式系统的个人理解小结

分布式系统的个人理解小结

分布式系统：分的微小服务，以小而独立的业务为单位，形成子系统。 然后分布式系统中需要有统一的调用，形成大的聚合服务。 同时，微服务群，需要有交流（通讯，注册中心，同步，异步），有管理（监控，调度）。 对外服务，需要有控制的对外开发，安全网关。
阅读更多...
Linux环境配置中问题小结

Linux环境配置中问题小结

在Linux环境配置中，遇到问题首先猜测： 1、是否是权限问题； 2、软连接是否配置；
阅读更多...
FHQ Treap模版（luogu P3369）

FHQ Treap模版（luogu P3369）

FHQ Treap模版（自用），带注释 #include<bits/stdc++.h>using namespace std;const int N=1e5+10;int n,root,idx;struct node{int l,r;int val,key,size;}tr[N];int getnew(int v){tr[++idx].val=v;//权值tr[idx].key=rand(
阅读更多...
long long,_int64使用小结

long long,_int64使用小结

前言： 　　在16位环境下，int/unsigned int 占16位，long/unsigned long占32位 　　在32位环境下，int占32位，unsigned int占16位，long/unsigned long占32位 何时需要使用： 　　long 和 int 范围是[-2^31,2^31)，即-2147483648~2147483647，而unsigned范围是[0,2^32)，
阅读更多...
密码学读书笔记小结

密码学读书笔记小结

密码学是保证消息的私密性和完整性以及消息认证的基础。加密算法的选择和密钥的管理是安全机制的效率、性能和可用性的关键。 公钥加密算法： 分发密钥比较容易，但是对大数据量的加密性能较差密钥加密算法： 更适合大批的加密任务混合型加密协议： 例如TLS，先用公钥加密建立一个安全通道，然后使用通道交换密钥，并将此密钥用于后续数据交换。 对分布式系统攻击的分类： 窃听： 未经授权获得消息副本伪装： 在未
阅读更多...
Android 源码中jni项目 加载so目录小结

Android 源码中jni项目 加载so目录小结

Android 源码中jni项目 加载so目录小结 文章目录 Android 源码中jni项目 加载so目录小结一、前言二、so目录验证测试1、jni so文件错误报错（1）报错1 - 未找到so文件：（2）报错2 - so文件中未找到native方法： 2、验证的几种情况（1）apk下面的 lib/arm64/ 放置正确的so文件（2）apk下面的 lib/arm64/ 放置错误的so文
阅读更多...
maven打包成可执行的jar，以及读取配置文件问题小结

maven打包成可执行的jar，以及读取配置文件问题小结

文章来源 https://blog.csdn.net/chasonsp/article/details/88852353 折腾的几天，使用maven打包后发现了问题，首先是打包的配置文件读取问题，使用getResource().getPah(）会发现在访问jar包的文件时，路径里会有感叹号（杠杠滴~~）是这样的 …jar!.. 经过不断的查找资料及反复验证后，终于找到了可行的方法：
阅读更多...
【硬刚大数据】Flink在实时在实时计算平台和实时数仓中的企业级应用小结

【硬刚大数据】Flink在实时在实时计算平台和实时数仓中的企业级应用小结

欢迎关注博客主页：https://blog.csdn.net/u013411339 欢迎点赞、收藏、留言 ，欢迎留言交流！本文由【王知无】原创，首发于 CSDN博客！本文首发CSDN论坛，未经过官方和本人允许，严禁转载！ 本文是对《【硬刚大数据之学习路线篇】从零到大数据专家的学习指南(全面升级版)》的面试部分补充。 大数据领域自 2010 年开始，以 Hadoop、Hive 为代
阅读更多...
Kafka常见问题学习路径源码阅读小结 | 写在Kafka3.0发布之际

Kafka常见问题学习路径源码阅读小结 | 写在Kafka3.0发布之际

严格来说，这篇文章也不是今天写的。是之前断断续续写在了几篇文章中。 2021年9月21日，随着Kafka3.0的发布，Kafka在「分布式流处理平台」这个目标上的努力进一步得到加强！Kafka不满足于「消息引擎」的定位，正式基于这样的定位，Kafka 社区于 0.10.0.0 版本正式推出了流处理组件 Kafka Streams，也正是从这个版本开始，Kafka 正式"变身"为分布式的流处理平台
阅读更多...
C++中继承及virtual小结

C++中继承及virtual小结

一、继承基础知识 C++中的继承 1.1继承的基本概念 类与类之间的关系 has-A，包含关系，用以描述一个类由多个“部件类”构成，实现has-A关系用类的成员属性表示，即一个类的成员属性是另一个已经定义好的类。 use-A，一个类使用另一个类，通过类之间的成员函数相互联系，定义友元或者通过传递参数的方式来实现。（和组合不同） is-A，即继承关系，关系具有传递性。 继承的特点 子类拥有
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2