【学习笔记】猫树

猫树是解决无修改区间或树上询问的高效算法, 对于线段树不好写 的问题, 可以考虑采用猫树, 构造 , 询问 , 空间 .

对于一个询问 , 如果 , 就可以直接得到答案, 否则我们考虑在线段树上定位, 它会在几个 处分开.

考虑第一次被分开的位置, 假设为 , 那么原来区间的就被分为 和 .

对于每个 预处理它向前的后缀缀, 即 答案, 对于它向后的前缀, 即 的答案.

如果我们知道了 所在位置, 我们可以直接合并 与 的答案即可.

不难发现预处理的复杂度是 , 总共 层, 每层每个数恰好被计算一次.

怎么快速知道 这个位置, 不难发现 就是 和 的 , 所以我们可以考虑 表预处理, 然后直接查询.

如果整棵线段树满足堆试储存 (即左子树编号为 , 右子树编号为 ) , 就有很好的性质.

对于任意深度相同的点, 它们的 是它们二进制下的 .

如果我们把整棵树建成一个满二叉树 , 那么对于任意一个区间 都是满足他们的深度是最深且在同一层的, 这很显然.

所以对于两个数 的二进制下的 为 , 这也很显然, 丢掉第一个不相同的位后面的所有位.

这样就实现了 询问.

__EOF__

本文作者： Lonely923 本文链接： https://www.cnblogs.com/Lonely923/p/16732410.html 关于博主： 评论和私信会在第一时间回复。或者直接私信我。 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！ 声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。

相关知识

猫树 学习笔记
【学习笔记】猫树
机器学习笔记
树猫
四上语文第6课《夜间飞行的秘密》学习笔记
#学习笔记# 最有...
猫爬架猫树猫跳台松木猫爬架猫窝猫抓木板剑麻柱猫树猫咪玩具 S9703
Cmisstree 喵想树 实木猫爬架猫窝猫树一体不占地剑麻猫跳台猫玩具树洞系列 399元
「猫树」猫树公司黄页
DIY猫树，简易猫爬架，简易猫树，猫树。#造型猫树 #简易猫

网址: 【学习笔记】猫树 https://www.mcbbbk.com/newsview1186632.html