划分树
引入
划分树是一种来解决区间第
建议先学完 主席树 再看划分树哦
过程
建树
划分树的建树比较简单,但是相对于其他树来说比较复杂。
如图,每一层都有一个看似无序的数组。其实,每一个被红色标记的数字都是 要分配到左儿子的。而分配的规则是什么?就是与 这一层的中位数 做比较,如果小于等于中位数,则分到左边,否则分到右边。但是这里要注意一下:并不是严格的 小于等于就分到左边,否则分到右边。因为中位数可能有相同,而且与
我们不可能每一次都对每一层排序,这样子不说常数,就算是理论复杂度也过不去。我们想,找中位数,一次排序就够了。为什么?比如,我们求 num[mid]
。
两个关键数组:
tree[log(N),N]:也就是树,要存下所有的值,空间复杂度
查询
那我们先扯一下主席树的内容。在用主席树求区间第
查询难理解的,在于 区间缩小 这种东西。下图,我查询的是
性质
时间复杂度 : 一次查询只需要
空间复杂度 : 只需要存储
亲测结果:主席树 :
划分树的应用
题意简述:给定一个
个元素的排列( ),有 m 次询问( ),每次删去排列中的一个数,求删去这个数之后排列的逆序对个数。
这题可以使用 CDQ 在
如果这道题改为强制在线,则一般使用树状数组 + 主席树的树套树解法解决,时间复杂度为
而使用划分树的话就可以在
注意:为了编程实现方便,本文依照位置的中间值将大数组划分为两个小数组,即下文中的划分树相当于是归并排序的过程,而非快速排序的过程。最顶层的大数组为有序数组,最底层为原数组。
对于每一个划分树中的节点,我们称他为右节点当且仅当他在下一层会被划分到右孩子,即原数组中位置比较靠后的那些数,相似的可以定义左节点。如果在建树的过程中将最顶层排为有序的,类似于归并排序求逆序对,可以发现一个数组的逆序对个数就是在每个左节点之前的右节点的个树和。
再考虑删除操作。删除一个左节点会将整个数组的逆序对减少在他之前右结点的个数,而删除一个右节点会减少在他之后的左节点个数。那么可以考虑每次动态维护“每一个左节点之前的右结点个数”和“每一个右节点之后的左节点个数”。这可以使用树状数组简单维护。
需要注意的是,在使用树状数组维护时只能计算在划分树中同一块内的贡献,而不能跳出块。对于树状数组来说有一个较为巧妙的处理方式。
考虑划分树上每一块的下标范围肯定为
[0001 0010] [0011 0100] [0101 0110] [0111 1000] [1001 1010] [1011 1100] [1101 1110] [1111 10000] lev=1
[0001 0010 0011 0100] [0101 0110 0111 1000] [1001 1010 1011 1100] [1101 1110 1111 10000] lev=2
[0001 0010 0011 0100 0101 0110 0111 1000] [1001 1010 1011 1100 1101 1110 1111 10000] lev=3
[0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 10000] lev=4
回忆一下树状数组的原理,在向上跳的时候,我们每次 x += lowbit(x)
。如果在向上跳的时候可以保证不跳出块,就可以保证只会影响到块内元素的值。向上查询也类似。
而如果要在向上跳的同时保证不跳出块,只需要保证在跳的时候满足
而向下跳则是完全不同的处理方式。每一块的下标如果使用 0-index 表示的话,即为
需要注意的是,按这一方法实现的树状数组会访问到的最大下标是距离 n 最近的 2 的整次幂,因此数组下标不能开 n。
由于需要在
附代码:
后记
参考博文 :传送门。
贡献者:@queenwen@WenzelTian@CCXXXI@kenlig@John@忘怀@mgt@orzAtalod@ksyx@zyouxam@danni@William@H-J-Granger@Ir1d
本页面最近更新:2/3/2023, 12:00:00 AM,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用