建设手机版网站需要主机多少空间/如何建立网站

Treap

普通二叉搜索树(BST)

• 对于任一棵子树，根节点权值大于左子树所有结点的权值，小于右子树所有结点权值

1. 结点结构体&初始化函数

struct BST{int l,r;int val;
}a[SIZE];
int tot,root,INF = 1<<30;
int New(int val){a[++tot].val = val;return tot;
}
void Build(){New(-INF),New(INF);//加两个无穷结点可以省很多事root = -1,a[1].r = 2;
}

2. 查询操作

• 如果递归到当前结点为空结点，则说明找不到
• 如果递归结点权值等于val，则返回当前结点
• 否则与查询对象val比大小，决定去左还是去右边

int Get(int p,int val){if(p == 0)return 0;if(val == a[p].val)return p;return val < a[p].val ? Get(a[p].l,val) : Get(a[p].r,val);
}

3. 插入操作

• 当前所指结点为空结点，则new一个新的，返回新结点编号
• 如果已经存在权值为val的结点，则不新建
• 当前结点权值与val比大小，决定递归左边还是右边，注意这里函数\(Insert\)函数的孩子“指针”参数为引用，可以实际修改。

void Insert(int &p,int val){if(!p){p = New(val);return ;}if(val == a[p].val)return;if(val < a[p].val)Insert(a[p].l,val);else Insert(a[p].r,val);
}

4. 寻找后继结点，即权值大于val的前提下，关键码最小的结点

• 如果存在一个权值为val的结点
  • 如果它有右子树，那么该子树最左边的结点就是val的后继结点
  • 如果没有，那么从root到该节点的路径上选一个权值符合的就是val的后继节点
• 根据当前结点权值与val作比较决定递归左子树或右子树，同时用当前结点更新答案（也就是看看这个点能否更新当前答案保存的后继结点）

int GetNext(int val){int ans = 2;int p = root;while(p){if(val == a[p].val){//找到了if(a[p].r > 0){//存在右子树p = a[p].r;while(a[p].l)p = a[p].l;//找右子树的最左边ans = p;}break;}if(a[p].val > val && a[p].val < a[ans].val)ans = p;//用路径上的点来更新p = val < a[p].val ? a[p].l : a[p].r;//决定递归结点}return p;
}

5. 删除结点

• 如果当前结点为空结点，返回
• 如果找到了
  • 如果只有一颗子树，那么把子树跟它的父亲连起来
  • 如果有两个子树，找到它的后继结点（也就是右子树的最左侧的结点），然后因为后继结点一定没有左子树，所以可以直接删除，然后将这个后继结点替换当前要删除的结点即可。
• 如果没找到就继续递归找

void Remove(int &p,int val){if(p == 0)return;if(val == a[p].val){if(a[p].l == 0)p = a[p].r;else if(a[p].r == 0)p = a[p].l;else{int nxt = a[p].r;while(a[nxt].l)nxt = a[nxt].l;Remove(a[p].r,a[nxt].val);a[nxt].l = a[p].l,a[nxt].r = a[p].r;p = nxt;}return;}if(val < a[p].val)Remove(a[p].l,val);else Remove(a[p].r,val);
}

Treap

由于升序或降序序列依次插入到BST中会导致二叉查找树查找效率退化，所以要在某些时刻进行适当调整。如果在new一个新结点的时候，给它随机赋值一个值，在满足BST的前提下，按照这个值去维护一个大顶堆(\(Tree+heap = Treap\))。那么期望下他的高度是相对较平衡的（感性理解，就是叶子结点的高度相差不多）

另外模板题 Luogo 3369 中每个相同权值的数有多个，加上还需要求排名等信息，所以Treap结点结构体如下

struct Treap{int l,r;int val,dat;int cnt,size;
}a[N];
int tot,root,n,INF = 0x7fffffff;
int New(int val){a[++tot].val = val;a[tot].dat = rand();//给随机权值赋值a[tot].cnt = a[tot].size = 1;return tot;
}
//更新当前结点所代表子树的size
void Update(int p){a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}
void Build(){New(-INF);New(INF);root = 1;a[1].r = 2;Update(1);
}

1. 查询数值x的排名

• 如果当前节点权值等于x，则返回该节点左子树size+1
• 如果当前节点权值大于x，那么返回左子树查询结果
• 否则返回右子树查询结果+左子树size+当前结点cnt(cnt为当前结点权值的个数)

int GetRankByVal(int p,int val){if(p == 0)return 0;if(val == a[p].val)return a[a[p].l].size + 1;//排名,+1if(val < a[p].val)return GetRankByVal(a[p].l,val);return GetRankByVal(a[p].r,val) + a[a[p].l].size + a[p].cnt;
}

2. 根据排名查询值

• 如果当前节点不存在，返回INF
• 如果当前节点左子树size大于等于rank，那么答案在左子树中
• 如果左子树size + 当前节点cnt 大于等于rank，那么答案就是当前节点的权值
• 否则答案在右子树中，减去左子树和当前节点的影响继续递归右子树即可

int GetValByRank(int p,int rank){if(p == 0)return INF;if(a[a[p].l].size >= rank)return GetValByRank(a[p].l,rank);if(a[a[p].l].size + a[p].cnt >= rank)return a[p].val;return GetValByRank(a[p].r,rank - a[a[p].l].size - a[p].cnt);
}

3. 右旋

void zig(int &p){int q = a[p].l;a[p].l = a[q].r;a[q].r = p;p = q;Update(a[p].r),Update(p);
}

4. 左旋

void zag(int &p){int q = a[p].r;a[p].r = a[q].l;a[q].l=p;p = q;Update(a[p].l),Update(p);
}

5. 插入

• 与BST大致相同，只是在把val插入到左子树或右子树时，要根据dat来维护Treap，即通过左旋或右旋调整使得堆性质成立
• 最后要Update

void Insert(int &p,int val){if(p == 0){p = New(val);return;}if(val == a[p].val){a[p].cnt ++;Update(p);return;}if(val < a[p].val){Insert(a[p].l,val);if(a[p].dat < a[a[p].l].dat)zig(p);}else{Insert(a[p].r,val);if(a[p].dat < a[a[p].r].dat)zag(p);}Update(p);
}

6. 获取前继节点和后继节点

int GetPre(int val){int ans = 1;int p = root;while(p){if(val == a[p].val){if(a[p].l){p = a[p].l;while(a[p].r) p = a[p].r;ans = p;}break;}if(a[p].val < val && a[p].val > a[ans].val)ans = p;p = val < a[p].val ? a[p].l : a[p].r;}return a[ans].val;
}
int GetNext(int val){int ans = 2;int p = root;while(p){if(val == a[p].val){if(a[p].r>0){p = a[p].r;while(a[p].l)p = a[p].l;ans = p;}break;}if(a[p].val > val && a[p].val < a[ans].val)ans = p;p = val < a[p].val ? a[p].l : a[p].r;}return a[ans].val;
}

7. 删除结点

• 因为Treap可以左旋或右旋，所以可以把要删除的结点进行左旋或右旋（旋转的时候要保证堆性质成立）到叶子节点进行删除

void Remove(int &p,int val){if(p == 0)return;if(val == a[p].val){if(a[p].cnt > 1){a[p].cnt --;Update(p);return;}if(a[p].l || a[p].r){//不是叶子结点，向下旋转if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat){zig(p),Remove(a[p].r,val);}else {zag(p);Remove(a[p].l,val);}Update(p);}else p = 0;//叶子节点，删除return;}val < a[p].val ? Remove(a[p].l,val) : Remove(a[p].r,val);Update(p);
}

附Luogu3369
Luogu3369

#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
struct Treap{int l,r;int val,dat;int cnt,size;
}a[N];
int tot,root,n,INF = 0x7fffffff;
int New(int val){a[++tot].val = val;a[tot].dat = rand();a[tot].cnt = a[tot].size = 1;return tot;
}
void Update(int p){a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}
void Build(){New(-INF);New(INF);root = 1;a[1].r = 2;Update(1);
}
int GetRankByVal(int p,int val){if(p == 0)return 0;if(val == a[p].val)return a[a[p].l].size + 1;//排名,+1if(val < a[p].val)return GetRankByVal(a[p].l,val);return GetRankByVal(a[p].r,val) + a[a[p].l].size + a[p].cnt;
}
int GetValByRank(int p,int rank){if(p == 0)return INF;if(a[a[p].l].size >= rank)return GetValByRank(a[p].l,rank);if(a[a[p].l].size + a[p].cnt >= rank)return a[p].val;return GetValByRank(a[p].r,rank - a[a[p].l].size - a[p].cnt);
}
void zig(int &p){int q = a[p].l;a[p].l = a[q].r;a[q].r = p;p = q;Update(a[p].r),Update(p);
}
void zag(int &p){int q = a[p].r;a[p].r = a[q].l;a[q].l=p;p = q;Update(a[p].l),Update(p);
}
void Insert(int &p,int val){if(p == 0){p = New(val);return;}if(val == a[p].val){a[p].cnt ++;Update(p);return;}if(val < a[p].val){Insert(a[p].l,val);if(a[p].dat < a[a[p].l].dat)zig(p);}else{Insert(a[p].r,val);if(a[p].dat < a[a[p].r].dat)zag(p);}Update(p);
}
int GetPre(int val){int ans = 1;int p = root;while(p){if(val == a[p].val){if(a[p].l){p = a[p].l;while(a[p].r) p = a[p].r;ans = p;}break;}if(a[p].val < val && a[p].val > a[ans].val)ans = p;p = val < a[p].val ? a[p].l : a[p].r;}return a[ans].val;
}
int GetNext(int val){int ans = 2;int p = root;while(p){if(val == a[p].val){if(a[p].r>0){p = a[p].r;while(a[p].l)p = a[p].l;ans = p;}break;}if(a[p].val > val && a[p].val < a[ans].val)ans = p;p = val < a[p].val ? a[p].l : a[p].r;}return a[ans].val;
}
void Remove(int &p,int val){if(p == 0)return;if(val == a[p].val){if(a[p].cnt > 1){a[p].cnt --;Update(p);return;}if(a[p].l || a[p].r){//不是叶子结点，向下旋转if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat){zig(p),Remove(a[p].r,val);}else {zag(p);Remove(a[p].l,val);}Update(p);}else p = 0;//叶子节点，删除return;}val < a[p].val ? Remove(a[p].l,val) : Remove(a[p].r,val);Update(p);
}
int main(){Build();scanf("%d",&n);while(n--){int opt,x;scanf("%d%d",&opt,&x);switch(opt){case 1:Insert(root,x);break;case 2:Remove(root,x);break;case 3:printf("%d\n",GetRankByVal(root,x)-1);break;case 4:printf("%d\n",GetValByRank(root,x+1));break;case 5:printf("%d\n",GetPre(x));break;case 6:printf("%d\n",GetNext(x));break;}}return 0;
}