生鲜网站模板,自己如何开网店,建设彩票网站制作,企业网站规划我想写在前面#xff0c;本文财阀世家全是虚构#xff0c;没有诋毁之意#xff0c;如有雷同#xff0c;纯属巧合 红色预警#xff01;#xff01;#xff01;红色预警 文章目录Scapegoat Tree概念模板变量声明Bad函数判断是否需要重构理解模板rebuild重构理解模板inser…我想写在前面本文财阀世家全是虚构没有诋毁之意如有雷同纯属巧合 红色预警红色预警 文章目录Scapegoat Tree概念模板变量声明Bad函数判断是否需要重构理解模板rebuild重构理解模板insert插入理解模板delete删除理解模板1删除排名为x的数模板2删除权值为x的数查找x排名理解模板找第K大理解模板前驱后继思路例题Tyvj 1728 普通平衡树题目code前言前言前言我觉得每次学新知识的时候动用生活中的常见现象来加以理解真的很
有趣有用最近梨泰院class真的上头太™爽了熟悉我博客风格的小伙伴应该了解
此内容是类比加以理解的并不是专业术语等类且模板的理解会在相应代码上方本篇可能已经在标题上告知了
用南韩小聋虾无恶意韩圈g应该懂电视剧中常见的财阀世家来进行替罪羊树理解话不多说赶紧上路Scapegoat Tree概念
在各种二叉平衡树中大多数的平衡树都是通过旋转来维护这棵二叉查找树的性质,splaysplaysplay旋转treaptreaptreap等等并且每次的查找的复杂度大概为logloglog的 在土地宽广的H国有着各种各样的领域每个领域都有领头羊家族势力贼™庞大 然而大家都心知肚明旋转很容易写挂十分玄学多转转说不定就A了已然成为我们的信条
但是越庞大的财阀世家越被其它公司所嫉妒因为势力体系时常发生戏剧般的扭转各个成员处心积虑争夺势力一点点把柄也很容易使它翻车 而替罪羊树餐饮界的巨头长家则是众多非旋转的二叉平衡树中比较好些也比较好理解的一种了通过一个神奇的东西以“亲情”稳固下文会介绍来达到与旋转平衡树差不多的效果。 数据结构最优美的莫过于最暴力却又仍然满足复杂度的数据结构了而且代码还™冗长易挂 替罪羊树作为数据结构的一员自然秉承着最暴力的思想 如果树的结构不够优美了发现自己两个儿子的势力出现严重不对等时可惜为时已晚即查找的复杂度要退化成O(n)O(n)O(n)或者比 O(log)O(log)O(log) 要大了那么就把这棵子树拍扁了重构就是重新洗牌的时候只要是为了长家亲情可以不要以前我喊你爸爸现在我是你祖宗也是有可能的 这样就能重新拥有二叉查找树优美的性质了让更有权的人做更高的位置维持整个家族的和谐。但是替罪羊树最大的缺陷就是无法对区间进行操作难以跨部门同时操作多个势力不像旋转的可以把子树转到一起非旋treaptreaptreap可以通过分裂合并完成 所以只要不搞区间替罪羊还是很有用的且无论在代码量和运行时间上都优于splaysplaysplay许多 我还是比较喜欢平衡树这种结构的 现在学习了三种平衡树 感觉替罪羊树像是一个人维护一根铁杆铁杆弯曲了的话强行掰直 SBT像是在杠杆上左右摇晃不断寻找平衡点 splay像是一个人单手托着装满豆子的盘子发现不平衡晃一晃就又平衡了… 不过还有奇葩的2-3-4树看图解感觉在有丝分裂… ------出处未知 由于是基于拍扁重构的所以替罪羊树思维难度小代码量小易于调试所以非常适合手残党使用 为了实现替罪羊树的平衡性引出了一个新概念平衡因子洗牌判定 平衡因子平衡因子平衡因子 平衡因子是为了判断这棵树是否平衡的一个系数 而在替罪羊树中这个平衡因子就是用来判断这一棵子树是否需要重构的标准常用alpha(α)alpha(α)alpha(α) 来表示 当以xxx为根这颗子树的满足 max(sz[lson],sz[rson])sz[x]∗αmax(sz[lson],sz[rson])sz[x]∗αmax(sz[lson],sz[rson])sz[x]∗α 时即左边或右边有一个子树所占大小超过了平衡因子的限定出现了严重的偏差时判断自己手下是不是势力足够庞大的时候自觉选择让位长大喜说过为了长家我们就可以对这颗子树进行重构了 一般 αα\alphaααα 取值为0.510.510.51左右普通题目一般取0.70.70.7左右就行了两个手下有一定能力不必要限制地太死可以观察谁更有能力得到更多人数支持多教孩子去杀鸡狗头。如果取的 α\alphaα 较大那么触发重构的次数就比较小所以插入的效率较高而查询的效率会相对较低反之则是频繁触发重构导致插入效率变低查询因为很稳定效率就会变高 其实我不太喜欢写死板概念本人爱好搞模板
模板
变量声明
背景简述在H国有个富可敌国好老套的霸道男主人设的财阀世家长家借用梨泰院class有着庞大的家庭成员链每个人都有不同的股份势力。而我们则是站在上帝视角来看这场权力纠纷的 exist该点是否真实存在Q干嘛呀A因为后面的删除不要慌 这个人是不是名存实亡势力是否还在自己手上 son[2]0左儿子1右儿子政策要求计划生育就生两个当自己的手下hhhh val该点的权值看题目给的是什么 上帝分配给这个娃儿的股份势力 alive子树不含自己中真正存在的点数和Q又在搞甚么A不要慌往下走看看站在自己阵营的势力人数有多少个现在还有股份势力的帮助自己与兄弟对抗 total子树中不含自己管它总的点数和管它是不是真的还存在 看看愿意站在自己阵营人数包括已经名存实亡失去势力的人员至少曾经帮过我尽管后面发现会直接扔掉它 memory[]idx2是自己手动的内存池自然idx2就是指针 cur[]idx1拍扁的数组和自己配置的指针用来重新洗牌打乱财阀集团的职位的工具 长家的亲情是建立在势力基础上的之前你是我爸爸是因为我势力不够一旦我翻身上位你就得叫我爸爸
struct Scapegoat {bool exist;int son[2], val, alive, total;
}t[MAXN];
int idx1, idx2, flag, root, Size;
int cur[MAXN], memory[MAXN];Bad函数判断是否需要重构
理解
其实上面介绍平衡因子的时候已经告诉了人数占比超过我们划分的界限说明孩子已经足够优秀了获得了大部分下人的支持尽管可能势力并不多呢老父亲你就自己乖乖下位吧 老父亲内心OS
模板
bool Bad ( int rt ) {return ( double ) t[rt].alive * alpha ( double ) max ( t[t[rt].son[0]].alive, t[t[rt].son[1]].alive );
}rebuild重构
理解
首先对于这棵子树要先进行拍扁从小到大的顺序左儿子-根-右儿子 然后把这个序列重新提起来如果要左右尽量平衡的话我们肯定是从中间开始提 很像线段树的递归方法 开始洗牌了这个部部长的两个手下也可以叫做两个儿子的能力体现已经很明显了下边人的站队已经有所明显对比部长就退位让儿子上自己卧薪尝胆一段时间说不定能再上
模板
void flat ( int rt ) {if ( ! rt )return;flat ( t[rt].son[0] );if ( t[rt].exist )cur[ idx1] rt;elsememory[ idx2] rt;flat ( t[rt].son[1] );
} void build ( int l, int r, int rt ) {int mid ( l r ) 1;rt cur[mid];if ( l r ) {t[rt].son[0] t[rt].son[1] 0;t[rt].alive t[rt].total 1;return;}if ( l mid )build ( l, mid - 1, t[rt].son[0] );elset[rt].son[0] 0;build ( mid 1, r, t[rt].son[1] );t[rt].total t[t[rt].son[0]].total t[t[rt].son[1]].total 1;t[rt].alive t[t[rt].son[0]].alive t[t[rt].son[1]].alive 1;
}void rebuild ( int rt ) {idx1 0;flat ( rt );if ( idx1 )build ( 1, idx1, rt );elsert 0;
}insert插入
理解
判断该点的权值与我们wanttoinsertwant to insertwanttoinsert的点的权值的大小关系小的往左儿子右的往右儿子 其实我们发现如果xxx发生重构有可能一路上的祖宗有颜色的点都会有所影响本应该找最上面第一个被影响的绿色然后重构下面就跟着完成了但是窝码的是一路上遇到就直接重构有颜色的都重构一遍 显而易见很浪费时间但是我不会另一种所以如果有dalao会的话麻烦教教蒟蒻 这样洗牌时从左到右的势力逐渐上升可以理解为势力过大的想去支持左边但是左儿子不稀罕势力过小的它反倒稀罕两兄弟可能口味不太一样吧hhhhh 其实它们很聪明的因为长家洗牌规则是取左右支持者差不多的人上既然自己选择了要小/大的就要把大/小丢给对方尽量保证自己站在中间位置当然了这一切都是假象毕竟上帝安排这娃儿成为谁的手下
模板
void insert ( int rt, int val ) {if ( ! rt ) {rt memory[idx2 --];t[rt].val val;t[rt].exist t[rt].alive t[rt].total 1;t[rt].son[0] t[rt].son[1] 0;return;}t[rt].alive , t[rt].total ;if ( val t[rt].val )insert ( t[rt].son[0], val );elseinsert ( t[rt].son[1], val );if ( Bad ( rt ) )rebuild ( rt );
}delete删除
理解
替罪羊的删除很有趣是一种惰性删除就是我不是真的把你删了只是给你打个删除标记等到重构的时候我不把你加进去自然而然你就消失了锁定一个点有两个方法权值或者排名我们可以把权值转化成排名用查找排名系统就可以了 你的势力已经被剥夺了但是你还是站在这里可以当个人形标志等重新洗牌的时候你就相当于被冷藏了调到了帕津不再在本部有任何痕迹一切为零
模板1删除排名为x的数
void Delete_rnk ( int rt, int rnk ) {if ( t[rt].exist t[t[rt].son[0]].alive 1 rnk ) {t[rt].exist 0;t[rt].alive --;return;}t[rt].alive --;if ( rnk t[t[rt].son[0]].alive t[rt].exist )Delete_rnk ( t[rt].son[0], rnk );elseDelete_rnk ( t[rt].son[1], rnk - t[t[rt].son[0]].alive - t[rt].exist );
}模板2删除权值为x的数
有时候删多了自己手底下一共的点还没有达到我们的期望也要进行一次重构 被革职的人太多了自己的支持人数其实已经不多了我们就进行一次洗牌统计巩固一下部门政权
void Delete_val ( int val ) {Delete_rnk ( root, FindRank ( val ) );if ( ( double ) t[root].total * alpha t[root].alive )rebuild ( root );
}查找x排名
理解
找排名其实跟treap,splaytreap,splaytreap,splay都是一路子先看左儿子发现排名没有左儿子真的存在的点多就在左儿子里面找不然就在右儿子里面找注意是真的存在的点因为我们是惰性删除看看势力从小到大的顺序自己排在第几位
模板
int FindRank ( int k ) {int rt root, ans 1;while ( rt ) {if ( k t[rt].val )rt t[rt].son[0];else {ans t[t[rt].son[0]].alive t[rt].exist;rt t[rt].son[1];}}return ans;
} 找第K大
理解
跟其他平衡树一样的的思路同样这里是要以真实存在的点来进行计算因为我们是惰性删除看看势力第K大的娃儿是哪个我们上帝没事还是要找点事做滴
模板
int FindKth ( int k ) {int rt root;while ( rt ) {if ( t[rt].exist t[t[rt].son[0]].alive 1 k )return t[rt].val;else if ( k t[t[rt].son[0]].alive )rt t[rt].son[0];else {k - ( t[t[rt].son[0]].alive t[rt].exist );rt t[rt].son[1];}}
}前驱后继
思路
根本不用单独写前驱后继那么复杂直接找到xxx的排名然后±1±1±1就是前驱后继了康康势力最接近与自己的比自己小的和比自己大的说实话要不是上帝要问问谁管你是谁影响老子上位 不同的题目不同的要求不同的写 什么意思呢我们以例题的要求为例 可能有多个值相同的数然后前驱要求严格小于后继要求严格大于 那么我们的写法就应该是
printf ( %d\n, FindKth ( FindRank ( x ) - 1 ) );
printf ( %d\n, FindKth ( FindRank ( x 1 ) ) );要理解我们的查找排名函数是排名找的是同值中最小的一个排名减一值一定变小了 而因为有同值所以我们就要手动把值加一再查找不管是否存在
例题Tyvj 1728 普通平衡树
题目
走一波~
code
#include cstdio
#include iostream
using namespace std;
#define MAXN 2000005
#define alpha 0.7
struct Scapegoat {bool exist;int son[2], val, alive, total;
}t[MAXN];
int idx1, idx2, flag, root, Size;
int cur[MAXN], memory[MAXN];bool Bad ( int rt ) {return ( double ) t[rt].alive * alpha ( double ) max ( t[t[rt].son[0]].alive, t[t[rt].son[1]].alive );
}void flat ( int rt ) {if ( ! rt )return;flat ( t[rt].son[0] );if ( t[rt].exist )cur[ idx1] rt;elsememory[ idx2] rt;flat ( t[rt].son[1] );
} void build ( int l, int r, int rt ) {int mid ( l r ) 1;rt cur[mid];if ( l r ) {t[rt].son[0] t[rt].son[1] 0;t[rt].alive t[rt].total 1;return;}if ( l mid )build ( l, mid - 1, t[rt].son[0] );elset[rt].son[0] 0;build ( mid 1, r, t[rt].son[1] );t[rt].total t[t[rt].son[0]].total t[t[rt].son[1]].total 1;t[rt].alive t[t[rt].son[0]].alive t[t[rt].son[1]].alive 1;
}void rebuild ( int rt ) {idx1 0;flat ( rt );if ( idx1 )build ( 1, idx1, rt );elsert 0;
}void insert ( int rt, int val ) {if ( ! rt ) {rt memory[idx2 --];t[rt].val val;t[rt].exist t[rt].alive t[rt].total 1;t[rt].son[0] t[rt].son[1] 0;return;}t[rt].alive , t[rt].total ;if ( val t[rt].val )insert ( t[rt].son[0], val );elseinsert ( t[rt].son[1], val );if ( Bad ( rt ) )rebuild ( rt );
}int FindKth ( int k ) {int rt root;while ( rt ) {if ( t[rt].exist t[t[rt].son[0]].alive 1 k )return t[rt].val;else if ( k t[t[rt].son[0]].alive )rt t[rt].son[0];else {k - ( t[t[rt].son[0]].alive t[rt].exist );rt t[rt].son[1];}}
}int FindRank ( int k ) {int rt root, ans 1;while ( rt ) {if ( k t[rt].val )rt t[rt].son[0];else {ans t[t[rt].son[0]].alive t[rt].exist;rt t[rt].son[1];}}return ans;
} void Delete_rnk ( int rt, int rnk ) {if ( t[rt].exist t[t[rt].son[0]].alive 1 rnk ) {t[rt].exist 0;t[rt].alive --;return;}t[rt].alive --;if ( rnk t[t[rt].son[0]].alive t[rt].exist )Delete_rnk ( t[rt].son[0], rnk );elseDelete_rnk ( t[rt].son[1], rnk - t[t[rt].son[0]].alive - t[rt].exist );
}void Delete_val ( int val ) {Delete_rnk ( root, FindRank ( val ) );if ( ( double ) t[root].total * alpha t[root].alive )rebuild ( root );
}int main() {int n;for ( int i 2000000;i 1;i -- )memory[ idx2] i;scanf ( %d, n );for ( int i 1;i n;i ) {int opt, x;scanf ( %d %d, opt, x );switch ( opt ) {case 1 : insert ( root, x ); break;case 2 : Delete_val ( x ); break;case 3 : printf ( %d\n, FindRank ( x ) ); break;case 4 : printf ( %d\n, FindKth ( x ) ); break;case 5 : printf ( %d\n, FindKth ( FindRank ( x ) - 1 ) ); break;case 6 : printf ( %d\n, FindKth ( FindRank ( x 1 ) ) ); break;}}return 0;
}作者bibi 刚开始就觉得这种数据结构都可以用皇宫生存法则来理解。 其实本来是想用227的举报同人圈事件的但是我怕被无脑举报想想还是算了但是我还是很不甘的毕竟我的太太都封笔了… 要知道学了splay是为了LCT那么学了替罪羊就是为了k-d tree
