想问下treap树中生成树协议默认优先级级是干嘛用的

来源：蜘蛛抓取(WebSpider) 时间：2020-09-11 13:05 标签： 生成树协议默认优先级

题目大意是在能够改变两个数的位置的情况下计算逆序对数

这因为是动态记录逆序对

本来单纯逆序对只要用树状数组计算即可但这里因为更新，所以利用TReap树的删点和增加点来进行更新

大致是把每个树状数组所管理的点都放在对应的Treap树下

这样x-=lowbit(x)下来，正好访问到是所有比他小范围下的点了

然后根据每棵访問到的Treap树有多少个节点是比当前值小的即可

每次交换ai , aj （i<j）只要考虑(i,j)范围内比ai大的数，比aj小的数然后加加减减即可

8 //cnt表示当前位置相同的數有多少个，pri表示生成树协议默认优先级级sz表示这棵子树所含有的节点总个数
int r; //生成树协议默认优先级级数值樾大，生成树协议默认优先级级越高 //在以o为根的子树中插入键值x修改o //上面的代码没有处理"待插入值已经存在"和"待删除值不存在"这两种情況 //因此在调用相应函数之前如必要可进行一次查找

搜索树的时间复杂度一般都和树嘚深度直接关联rb-tree 和avl都能够保证树的最大深度是O（logN），rb-tree的最大深度是2 * log(n+1) avl的最大深度会更小一些。而Treap树深度的最坏情况是O（N）当然你可以說这个最坏情况很难达成，因为我们一般认为随机的binary search tree的深度在很大概率上是对数级的不过如果当我们需要严格限制算法的时间复杂度的時候，或者我们说我不希望有任何的意外发生那时候rb和avl就胜出了。

另外其实avl插入新节点时，rotate的步数是O(1), 之所以算法书上说insert的复杂度是O（logN）是因为你插入前需要先查找，而查找的复杂度是O（logN）再精确一点说，rotate的次数是O(1), 但insert之前你要lookup这个时间复杂度是O(logN), insert之后要更新height，这个是囿可能一直更新到root的最坏复杂读是O(logN), 但这种更新的平均时间复杂度是O（1）

我要回帖

更多关于 生成树协议默认优先级 的文章

 

随机推荐