加载中...

zkw线段树

发表于2023-08-08|OI（高中）2023-2024赛季

|总字数:277|阅读时长:1分钟|浏览量:

zkw线段树

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132177887

启蒙题： http://zhengruioi.com/problem/2609

参考论文： https://wenku.baidu.com/view/f27db60ee87101f69e319544.html?wkts=1691491614153

不用递归，通过位运算实现的线段树。（本质：线段树为一颗满二叉树）

如果值域为 $V$ ，那么zkw只能维护到 $V-2$ 的值域，所以最简单的方法就是变成 $2^{n+1}$

由于叶子节点占总节点数的一半，所以原序列第 $x$ 位置对应线段树 $x+M$

对于区间问题，一个性质，线段树访问的区间必然是前面是连续一段右节点，后面是左。

一对兄弟节点，左边末尾为0，右为1

处理时要把 $[l,r]$ 变成 $[l-1, r+1]$ ，结合下图和代码理解在这里插入图片描述

也就是我们一直让我们现在的 $l$ 为左节点，然后访问其右节点

单点修改，区间求min：

在这里插入图片描述

文章作者: zhangxixi

文章链接: http://zhangxixi2008.github.io/post/bc52ed8a

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！

算法数据结构

相关推荐

线段树记录系数维护动态信息：ZR2612

线段树记录系数维护动态信息：ZR2612 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132255084 http://zhengruioi.com/problem/2612 ai+bj≥0a_i+b_j\ge 0ai+bj≥0 => ai≥−bja_i\ge -b_jai≥−bj 因此考虑把 bbb 去负， ai≥bja_i\ge b_jai≥bj 也就是一个区间 aaa 最小值大于 bbb 最大值套路1 （大小关系转不同）对于此...

【GDOI2022PJD2T4 机器人】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16191401.html D2T4 机器人题目刚上初一的小纯特别喜欢机器人，这周末，她报名了学校的“小机器人俱乐部”，而进入俱乐部需要通过一场考试。考试场地可以看作一个 n×mn \times mn×m 的网格图，行从上往下标号为 1,…,n1, \dots, n1,…,n，列从左往右标号为 1,…,m1, \dots , m1,…,m。每个格子有三种可能：空地，障碍物，机器人（有且只有一个），分别用“.”、“*”、“R”表示。现在小纯需要...

线段树分治

线段树分治本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132126153 https://www.luogu.com.cn/problem/P5787 理解：操作离线用时间线段树维护整体统计答案，进入到某个节点加入，离开时撤销可以用可撤销数据结构维护（可能可以可持久化或LCT维护？以后再学）

点分治小结

点分治小结本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217048 https://www.luogu.com.cn/problem/P3806 dfs1：找到当前重心 dfs2：统计当前每个点到重心的距离 dfz：点分治找重心，处理出 xxx 所有儿子子树和非 xxx 子树的大小最大值，这个最大值最小的点 xxx 就是答案注意这个过程中统计非 xxx 子树大小需要统计当前分治区间的大小 sumsumsum ，要时刻注意维护这个...

【P1270 “访问”美术馆】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600574.html 题目链接典型的树形dp。设 dp(x,i)dp(x, i)dp(x,i) 表示 xxx 的子树内逗留 iii 秒的作品最大值。 dp(x,i)=max⁡y∈xmax⁡i=0smax⁡j=2×zidp(y,j−2×z)−dp(x,j−i)dp(x, i)=\max_{y\in x}\max_{i=0}^s\max_{j=2\times z}^i dp(y,j-2\times z)-dp(x,j-i) dp(x,i)=y...

cqd分治思想

cqd分治思想本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132135114 https://www.luogu.com.cn/problem/P3810 常用于维护三维偏序问题，对于相等的情况处理我感觉不太好，之前ABC打cdq被制裁了三维，第一维显然排序分治，所以第二维很明显了。因为只需要考虑左对右的贡献，所以黑白染色一下，再按b排即可。然后黑白一个对应查询一个对应修改操作。最后一个拿树状数组

数据加载中