线段树合并思想
线段树合并思想
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132135188
直接维护很大，所以每个节点动态开点。
合并时按顺序，一个有一个没直接把有那个连上去。
否则递归。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-08
zkw线段树
zkw线段树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132177887 启蒙题： http://zhengruioi.com/problem/2609 参考论文： https://wenku.baidu.com/view/f27db60ee87101f69e319544.html?wkts=1691491614153 不用递归，通过位运算实现的线段树。（本质：线段树为一颗满二叉树） 如果值域为 VVV ，那么zkw只能维护到 V−2V-2V−2 的值...
2026-06-16
算法复键——树状数组
算法复键——树状数组 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162026675 树状数组怎么被我忘光了？？？ 1. 干什么的 简单来说，树状数组支持一下两种操作： 单点加 查询前缀和 →\to→ 区间和查询 如果我们记录的是差分数列，那样子可以也可以实现： 区间加 单点查询 不一定是求和，所有满足交换律的都可以用树状数组实现。比如区间积、区间XOR 2. 怎么实现 现在以单点加、求前缀和为例： 我们定义一种操作 lowbit...
2023-08-10
点分治小结
点分治小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217048 https://www.luogu.com.cn/problem/P3806 dfs1：找到当前重心 dfs2：统计当前每个点到重心的距离 dfz：点分治 找重心，处理出 xxx 所有儿子子树和非 xxx 子树的大小最大值，这个最大值最小的点 xxx 就是答案 注意这个过程中统计非 xxx 子树大小需要统计当前分治区间的大小 sumsumsum ，要时刻注意维护这个...
2023-08-10
李超线段树
李超线段树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217504 插入过程中，先询问中点，让 uuu 在上，它必然覆盖其中一个区间。 然后看看左右端点哪里 vvv 比 uuu 大，就在对应区间递归下去
2023-08-05
兔队线段树：楼房重建
兔队线段树：楼房重建 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132126096 https://www.luogu.com.cn/problem/P4198 本质：在线段树上每个节点维护信息时再深入到底部，加个 log\loglog O(nlog2n)O(n\log^2n)O(nlog2n) 总比 O(n2)O(n^2)O(n2) 优。 抽象到本题，就是对于每个线段树节点单独维护只考虑这个区间的答案。 合并的过程，显然左子树可以直接继承，所以可以...
2023-08-25
树套树小结
树套树小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132501426 树状数组套权值线段树，实现过程类似主席树，采用动态开点实现 https://www.luogu.com.cn/problem/P3380 树状数组部分 线段树部分