线段树杂笔

· · 个人记录

线段树杂笔

[TOC]

扯

滚回来复习...

东西可能挺杂而且挺乱的...

由于是复习 所以一些东西写的不会很详细

BS 读了一下 发现这已经不是乱不乱的问题了 而是基本没有什么实质性的东西 所以不建议阅读

以下内容过于扯淡 所以可能引起您的不适 慎重阅读(轻点骂)

线段树

多用于处理区间问题 是分块思想的树化 对于信息处理的二进制化 分块与线段树相似性挺大的 分块就像是一棵只有三层的线段树 分块复杂度是根号的 有的时候不能高效的解决问题 所以就有了线段树这一 \log 级别的数据结构

线段树只能维护可结合的信息 分块更为灵活

越暴力的算法可以支持的操作就越多 看那 n^2 的暴力不是想怎么玩怎么玩

题目

对于题目 一般需要考虑线段树节点维护的信息 子节点向父节点信息的合并等问题

这里吧前面做过的部分题目搬过来了...

P5568 [SDOI2008] 校门外的区间

把问题转化一下

U$: 区间 $[l, r]$ 赋值为 $1 I$: 区间 $[1, l)$ 和区间 $(r, n]$ 赋值为 $0 D$: 区间 $[l, r]$ 赋值为 $0 $S$: 区间 $[l, r]$ 取反 然后把一个点拆成两个处理区间开闭的问题 线段树直接做就可以了 --- [代码](https://www.luogu.com.cn/paste/43s5tt1y) --- **P2572 [SCOI2010]序列操作** 线段树的好题 以为要调许久 写完崩了一发直接过了??? --- 前两个操作时区间覆盖 第三个操作区间翻转 第四个操作是区间和 都是基础操作 考虑最后一个操作怎么维护 区间中连续的 $1

在线段树的每个节点上维护前缀 1 的个数后缀 1 的个数 即可通过两个子节点合并得到父节点信息 再维护每个节点内的连续的 1 的个数取较大值即可

合并的时候需要分情况讨论进行拼接

然后考虑修改的时候怎么维护

区间覆盖直接平推就好了 但是区间翻转比较麻烦

可以对应的再维护前缀 0 后缀 0 区间中连续的 0 的个数 区间翻转的时候直接交换就好了

查询操作比较难写 所以就直接写成重载运算符合并的形式了 时间卡的不是很紧的话是没有问题的

代码

P5522 [yLOI2019] 棠梨煎雪

比较经典的线段树题

首先比较好想的是可以直接上拆位线段树

开三十棵线段树 维护 m 个串的每一位 修改和查询都在三十棵树上做就好了

在每棵线段树上维护 m 个串上这一位的数字 以及区间中 1 的个数和 0 的个数 ? 对数字个数不做贡献

查询的时候在每一位上把这个区间中 0 和 1 的个数都取出来 如果都为 0 那么这一位是可以任意取的 如果均不为 0 则对答案没有贡献

假设所有位上都至少有一个为 0 然后有 cnt 个两个都为 0 的位 答案就是 2^{cnt}

复杂度 O(nq\log m)

期望得分 70

代码

最后一部分数据是过不去的 那个 n 的常数好像有点大 尽管 n 只有 30

把每个串压到一个数里面 线段树里直接维护这 $m$ 个串 将所有的 $?$ 看做 $1$ 维护一个 $0$ 的串和一个 $1$ 的串 同时维护区间 $01$ 串的与 查询的时候 把这个区间的 $0$ 串和 $1$ 串取出来 依旧判断每一位即可 复杂度 $O(q(n + \log m))

代码

P6327 区间加区间sin和

比较奇怪的线段树

来自数学的公式:

\sin(\alpha + \beta) = \sin\alpha\cos\beta + \cos\alpha\sin\beta\\cos(\alpha + \beta) = \cos\alpha\cos\beta - \sin\alpha\cos\beta

然后就可以乘法分配律直接做了

代码

权值线段树

这么一写感觉权值线段树的东西好像挺多的

对权值作为维护对象开的线段树 每个点存的是区间内对于数字的某种信息 一般来说 最常见的是出现次数

一般的线段树是对序列建树 权值线段树则是对值域建树

权值线段树的时空复杂度是与值域有关的

一般配合离散化使用

然后是模板题

显然找不到模板题 所以只能抓这道题来凑数了(雾

P3369 【模板】普通平衡树

插入和删除相当于单点加 查询某个数的排名相当于区间和 查对应排名的数和前驱后继自己想一下就好了

在这道题目的条件下 线段树跑的是比 splay 要快的

代码

权值树的加减

权值树是支持加减的 对应节点相加减 得到的还是一颗权值树

维护权值树的前缀和就可以将权值树从全局问题推广到区间问题

对于每个点 建一棵权值树 第 k 棵树维护 [1, k] 区间的出现次数

当询问区间 [l, r] 中的 k 大值的时候 可以用 [1, r] 的树减去 [1, l - 1] 的树 得到 [l, r] 的树 在这棵树上找 k 大值就好了

空间的话动态开点即可

扔一道模板题

P3834 【模板】可持久化线段树 2（主席树）

啥? 难道上面扯了这么多你没看出这就是主席树?(大雾

主席树: 可持久化权值线段树

代码

权值树的分裂与合并

上面已经写道了权值树是可以加减什么的 也可以直接把某一段抠出来之类的东西

那么当然也可以干一下拆了按 按了拆之类的事情

其实这一块的东西直接看代码就能懂

合并

比较好写也比较简单 就是感觉时空复杂度有点玄学...

大概这东西的用处就是把两棵树合成一棵(废话)

同时树中维护的信息也是可以合并的 这样可以将多棵树中的信息汇总到一棵树上 方便查询

维护一些其他数据结构不太好维护的信息 一般的是维护一些树上问题 大概是对于在每个点上开线段树进行维护的东西都可以用合并来搞

大概就是一些查询子树内的前后驱 第 k 大 或者 x 是第几大 出现最多的数 总和最大的数之类的用权值线段树能干的事

然后扔题目

啥? 上面扯了这么多你还没看出来这是线段树合并?(巨雾

CF600E Lomsat gelral

比模板题还要模板的模板题

在每个点上维护一棵线段树 然后 dfs 一遍 向上暴力合并即可

代码

P4556 [Vani有约会]雨天的尾巴

是模板题但又不是很模板的模板题

把路径差分 在每个点上维护一棵线段树 维护对应颜色的数量 两个端点的位置加一 lca 和 lca 的父亲位置减一 最后 dfs 一遍 向上暴力合并即可

代码

P3224 [HNOI2012]永无乡

和板子题差不多板子的板子题

在每个点维护一个权值线段树 维护并查集判断联通情况 合并并查集的时候把线段树暴力合并即可

查询即在当前连通块内查就好了

代码

P3605 [USACO17JAN]Promotion Counting P

连当板子题都不配的弱化版板子题

依旧是每个点维护线段树 dfs 暴力合并 查询区间和即可

代码

更多的题目后期再补 这里留坑

分裂

感觉和无旋 treap 差不多的亚子

直接扔题目

啥? 线段树合并都有了? 你猜不到下一个就是线段树分裂?(神雾

P5494 【模板】线段树分裂

代码

好像并没有什么别的题了

其实还找到了两道的 但是并不会做...

所以就咕了

权值树的加减(扩展

既然可以前缀和差分啥的 当然可以用树状数组和线段树来维护前缀和了

留坑 待填...

zkw 线段树(假)

线段树的循环加速

zkw 线段树能干的一般线段树都能干 一般线段树能干的 zkw 线段树不一定能干

Q: 所以这东西有什么用呢

A: 没用

好 不学了

zkw 线段树相较于一般的线段树(指递归式)的跑的比较快 一般来说代码简单 但是适用范围不如一般的线段树 比如不能处理运算优先级的问题

对于单点修改区间查的这种东西还是非常好用的 话说为什么不用树状数组

所以这东西确实没有用

zkw 线段树在没有区间修改操作的时候 对于单点查询的复杂度是 O(1) 的 且对于单点修改和区间查询的操作非常容易实现 但是不如树状数组容易

所以这东西真的没用

单点修改直接暴力修改 区间求和转为开区间处理

当出现区间修改操作的时候 代码就会比较复杂 所以还是写递归线段树吧... 需要标记永久化

感觉一般的题目也不会特意的卡递归线段树 所以不再展开了

扔一个地址