算法本质看了一下 UOJ 评论区。。。其实就是将分治进行离线,我们用一个东西来存储这个分治结构,以及前面按位置分治的答案。所以这个算法最重要的还是,寻找特定问题的分治方案。例题讲解区间最大子段和题意给你一个序列 aiai ,有 mm 次询问,每次询问一个区间 [l,r][l,r] ,表示询问这段区间的最大子段和。
猫树 学习笔记 Ref:https://immortalco.blog.uoj.ac/blog/2102 猫树 解决无修改序列区间查询问题。预处理O(nlogn)O(nlogn),询问O(1)O(1),空间复杂度O(nlogn)O(nlogn)(假设合并信息复杂度为O(1)O(1))。 将原序列长度扩展成2n2n,用堆式存储(rtrt的左(右)儿子为rt∗2+0(1)rt∗2+0(...
参考文献: https://immortalco.blog.uoj.ac/blog/2102 https://www.luogu.com.cn/blog/command-block/yi-suo-chang-yong-di-shuo-ju-jie-gou-wei-hu-shou-fa
http://immortalco.blog.uoj.ac/blog/2102 https://www.cnblogs.com/Judge/p/10475728.html 板题: https://www.luogu.com.cn/problem/P3865 注意点: 猫树的语处理的数组的存法:同一深度的区间互不相交,所以记二维数组,第一维是深度,第二维是位置。 猫树的核心在于快速求lca,所以需要把线段树长度搞成2tp2...
一个非常 trivial 也不太常见的算法,不过学过了就不要忘了哦( 猫树问题可以适用于离线解决以下类型的数据结构问题: - 与序列有关,且询问是一段区间 - 序列静态,即,不涉及修改操作 当然离不离线都可以,由于其过程类似于点分治,所以在线的情况可通过类似于建出建出点