Java教程

关于线段树的一些魔幻操作[学习笔记] 转自xyz32768

本文主要是介绍关于线段树的一些魔幻操作[学习笔记] 转自xyz32768,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

转自:https://blog.csdn.net/xyz32768/article/details/84398038

引入

  • 众所周知,线段树可以维护序列,进行区间操作
  • 单点加 + 区间求和
  • 区间加 + 区间求和
  • 区间加 + 区间乘 + 区间求和
  • (省略.......)
  • 但是有些操作呢,又不能像上面这三个问题一样通过简单的打标记 + 提取区间解决
  • 仍需要用到一些\(trick\)

一、势能线段树

  • 我们知道,线段树能够通过打标记实现区间修改的条件有两个:
  • \(1.\)能够快速处理标记对区间询问结果的影响
  • \(2.\)能够快速实现区间的合并
  • 但有的区间修改不满足上面的条件
  • 但某些修改存在一些奇妙的性质,使得序列每个元素被修改的次数有一个上限
  • 可以在线段树每个节点上记录一个值,表示对应区间是否每个元素都达到了修改次数的上限
  • 区间修改时暴力递归到递归到叶子节点,如果在这个途中碰到了一个节点,这个节点对应的区间内的每个点都已经达到了修改次数上限,就直接\(return\)掉
  • 可以证明时间复杂度为\(O(nlogn)\) * 区间修改次数上限
  • 可以举几个简单例子说明一下

区间开平方,区间求和

  • 一个数\(x\)被开平方\(O(loglogx)\)后会变成\(1\)或\(0\),当然是向下取整不考虑小数,继续开根后不变
  • 所以线段树节点上用一个变量记录是否区间内全为\(1\)或\(0\)
  • 修改递归到叶子的时候,如果达到了区间内全为\(1\)或\(0\)的节点就\(return\)掉
  • 复杂度O(nlognlogx)

区间取模,区间求和

  • 一个数\(x\)对\(p\)取模,如果\(x \geq p\)则\(x\)至少变小一半,前置知识
  • 此时每个节点维护当前对应区间的和以及区间最小值
  • 区间对\(p\)取模时仍然递归到叶子
  • 如果某个节点对应的区间最小值小于\(p\)直接\(return\)掉
  • 复杂度\(O(nlognlogx)\)

区间除(向下取整),区间加,区间求和

  • 区间内的数整除\(1\)是无效的,直接跳过即可
  • 否则整除一个数会使得区间内最大值与最小值的差至少减少一半
  • 维护区间最小值和最大值以及区间和,区间懒标记
  • 整除时递归到叶子即可
  • 如果某个节点对应的区间\(max/d - max == min/d - min\),那么就说这个节点对应的区间的内的所有数都相等了,我们就不用暴力往下更新了,直接\(return\)即可,否则的话还是暴力到叶节点。
  • 因为区间加减都是一个数的话是不会影响最大值和最小值的差的,所以我们还是最多做log(max-min)次暴力就可以了,后面都是直接算答案\(return\)的
  • 时间复杂度\(O(nlog(max-min) + nlogn)\)
  • 例题:LOJ#6029 2017雅礼集训

二、李超线段树
利用标记永久化维护区间内的优势线段的数据结构。
具体详情可移步这里

三、线段树维护单调子序列(注意不是必须连续)

  • 考虑经典问题
  • 给定一个序列,支持单点修改
  • 询问给出\([l.r]\)
  • 求有多少个\(i∈[l,r]\)满足\(i = l\)或者\([l,i-1]\)内的任何一个数都不大于第\(i\)个数
  • 换句话说,求\([l,r]\)内有多少个位置\(i\)是\([l,r]\)内对应的以\(i\)结尾的前缀最大值
  • 定义函数\(query(u,x)\)
  • 表示当前线段树\(u\)节点对应区间内,有多少个数是\(\geqx\)并且是对应区间内的前缀最大值
  • 线段树上维护区间最大值
  • 如果\(u\)对应的区间最大值\(< x\) 那么很明显 \(quey(u,x) = 0\)
  • 设\(u\)的左右子树分别为\(lc\)和\(rc\)
  • 如果\(lc\)的最大值\(< x\),那么\(queey(u,x) = query(rc,x)\)
  • 否则的话,因为左子树肯定是在右子树的前缀里面,所以此时\(query(u,x) = query(lc,x) + query(rc,max_lc)\)
  • 其中\(max_lc\),表示\(lc\)节点对应区间内的最大值
  • 注意到\(query(rc,max)\)仅和\(u\)有关的,或者参数不存在变量
  • 所以在节点\(u\)上存储一个变量\(ri_u = query(rc,max_lc)\)即可
  • 这样就能通过\(O(nlogn)\)的建树之后\(O(logn)\)查询了
  • 修改时直接重新计算\(max\)和\(ri\),\(O(log^2n)\)
  • 询问时把区间\([l,r]\)拆成线段树上的\(m\)(不超过\(O(logn)\))个区间\([l_1,r_1],[l_2,r_2],...,[l_m,r_m]\)
  • 设对应的节点分别为\(u_1,u_2,...,u_m\)
  • 并设\(pre\),初始为\(-INF\)
  • \(i\)从\(1\)到\(m\),重复\(m\)次下面的操作
  • (1)将\(query(u_i,pre)\)加进询问结果
  • (2)如果\(query(u_i,pre) \neq 0\),则\(pre <- max_{u_i}\)
  • 复杂度\(O(log^2n)\)
  • 总复杂度\(O(nlog^2n)\)
这篇关于关于线段树的一些魔幻操作[学习笔记] 转自xyz32768的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!