KI子线段树 / AKEE SegmentTree
2021/7/1 6:22:22
本文主要是介绍KI子线段树 / AKEE SegmentTree,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
背景
你 Ki 叔 最近 CF 虐场的同时发明了一种趣味的东西,适用于区间修改查询问题,但合并两个区间的贡献复杂度需要与区间长度有关的问题,这种问题无法用普通线段树去维护,因为复杂度爆炸,过去一般会使用分块维护,需要讨论散块、整块等问题,较为复杂,而神仙大 Ki 子研究出了一种新的方式,代码好写,想法基于在线段树上对节点大小进行根号分治。
理论
理论具体来说:
- 设立一个阈值 \(B\)
- 修改的时候,对于线段树节点大小 \(\le B\) 的节点,暴力 pushup,\(> B\) 的时候则不管。
- 查询的时候,只有当前节点完全属于查询区间且节点大小 \(\le B\) 时,在该点上相应查询。
写起来很好写,就 pushup 和 query 的时候加一个 if 条件就行。
事实上,相当于是舍弃了线段树上方一部分的结构,也可以理解维护了 \(\frac{n}{B}\) 级别颗线段树。
这样做复杂度是啥子?设 pushup 一个长度为 \(a\) 的区间的复杂度是 \(O(a \times X)\),查询一个线段树节点的答案复杂度是 \(O(Y)\)。
- 考虑 Pushup。根据线段树理论每层只会递归到两个节点,因此区间总长度是 \(B + \frac{B}{2} + \frac{B}{4} + \dots = 2B\) 级别的,复杂度是 \(O(B \times X)\)
- 考虑 Query,定义最高层是节点大小 \(\le B\) 最大的那一层,递归到最高层下面的最多两个区间,复杂度应当是 \(O((\frac{n}{B} + \log B) \times Y)\),通常 \(\log\) 要小,可以视为 \(O(\frac{n}{B} \times Y)\)
这个均摊大概是 \(B = \sqrt \frac{nY}{X}\),总复杂度 \(O(q\sqrt{nXY})\)。
例 1:CF1540D. Inverse Inversions
题目
经过若干步转化,问题变为维护一个序列 \(b\),若干次查询:
-
\(b\) 单点改
-
给一个值 \(v\),以及 \(p\),执行:
for i = p; i <= n; i++: if v >= b[i]: v++
输出最后的 \(v\)
考虑进行一段区间的这样操作,设 \(f(x)\) 为把 \(x\) 丢出去出来的会是啥,这个函数是连续不降的,函数不同的值只有区间长度种,可以分段维护函数,考虑合并的时候可以用类归并的方式 \(O(长度)\) 合并。
查询的时候直接按顺序在维护分段函数上二分 / lower_bound 就行。
这样复杂度是 \(O(q\sqrt{n \log n})\)。
ki 叔代码
例 2:CF1129D Isolation / [BJOI2017]开车
链接 1 / 链接 2
两题最后可以转化为这样一个数据结构问题:
有 \(n\) 个东西排成一排 ,有两个属性 \(a_i, b_i\),每次:
- 给 \([l, r]\) 区间的 \(a\) 加减一个权值 \(w\)
- 询问一个区间 \([l, r]\) 中,所有 \(a\) 在区间 \([x, y]\) 的 \(b\) 的和。
对于一个区间,可以维护按 \(a\) 排序的结果并且预处理 \(b\) 前缀和,查询就可以在上面二分做到 \(\log\),而排序可以从下面两个儿子线性归并排序。
复杂度是 \(O(q\sqrt{n\log n})\) 的。
这比传统的分块,把 \(\log\) 放根号里了,但事实上原本也可以做到,只不过仍然需要在散块中归并排序,其实与 ki 子线段树原理本质是一样的,但这个统一且和谐,简单很多!
这两题确实也有没有 \(\log\) 做法,是开一个桶,但依赖于相邻两个值差不超过 \(1\) 这种限制。
这篇关于KI子线段树 / AKEE SegmentTree的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?