Limit 的线段树题单总结

# Limit 的线段树题单 总结

## 题目

P6186：求序列 $k$ 次冒泡排序后的逆序对数量，复杂度 $O(q\log n)$。

P6492：一个仅含``L``与``R``的字符串，字符单点修改，查询最长的``LR``交替的字串，复杂度 $O(q\log n)$。

CF620E：一棵树，$60$ 种颜色，初始每个节点有颜色，修改子树颜色，查询子树颜色种数，复杂度 $O(q\log n)$。

P2894：一个序列，初始全为$0$。两种操作：将最前的连续的长至少为 $x$ 的全为 $0$ 的子序列全变为 $1$；或将一区间变为 $0$，复杂度 $O(q\log n)$。

P2894：一个字符串，每次将一区间重排为字典序最小的回文序列，求最终字符串，复杂度 $O(q\log n)$。

CF431E：一个序列，修改单点值，查询 $k$，使得 $v$（查询时给定）减去前 $k$ 小的序列元素之和再除以 $k$ 的结果最小，且这个结果比前 $k$ 小的元素都不小。$O(q\log^2 n)$ 能过，但有 $O(q\log n)$ 解法。

P2184：一个序列，修改时在一区间中放一种元素，查询区间元素种类，复杂度 $O(q\log n)$。

P1438：一个序列，查询时将一个区间加上一个等差数列，单点询问，复杂度 $O(q\log n)$。

CF992E：一个序列，单点修改，询问是否有一个元素等于其前的所有元素之和，复杂度 $O(q\log n)$。

P1972：一个序列，元素最大为 $10^6$，无修改，询问区间内有多少种数字，复杂度 $O(q\log n)$。

CF1000F：一个序列，元素最大为 $10^6$，无修改，询问区间内有没有只出现一次的数字，复杂度 $O(q\log n)$。

CF1422F：一个序列，没有修改，但强制在线，求区间最小公倍数，模数为质数，复杂度 $O(q\log n)$。

CF1004F：一个序列，单点修改，查询有多少个区间按位或和至少为 $x$。数字最多$20$ 位，复杂度 $O(q\log^2 n)$。

CF1114F：一个序列，修改区间乘上一个数，查询区间乘积的欧拉函数，复杂度 $O(q\log^2 n)$。

P4145：一个序列，修改将区间开平方根，查询区间和，复杂度 $O(q\log n)$。

CF446C：一个序列，修改将区间加上斐波那契数列，查询区间和。

P1471：一个序列，区间修改，查询平均数或方差。

P3300：一个最大 $10^5 \cdot 6$ 的矩形，每一格可以和上下，左右，上下左右联通或不连通（空）。单点修改，查询一个宽完整但长不完整的矩形中，有多少含楼房（一部分上下左右联通的格子为房子）的连通块。

P4839：一些桶，修改时往一个桶中加入一个元素，查询时查询区间中桶中元素的最大异或和。

## 思路类型

### 拆贡献

将计算多次计算所有元素的贡献和，改为分别计算每个元素的贡献，再将其处理为所求答案。

### 拆二进制位

处理位运算相关问题时，位运算的各位**独立**，所以可以把一个数拆成 $32$ 位，再分别处理。

### “前后缀区间”类线段树

需要求“最长合法区间”时，可以用线段树维护每个区间的前后缀最长合法区间。查询时两个相邻节点的前后缀拼在一起，再取最优就是答案。

### 树的序列化（DFS序）

按DFS的访问顺序将每个点重新编号，此时子树内的编号连续，可以将子树修改查询转换为线段树。

### 字符串类线段树

开 $26$ 个线段树并分别维护，或开 $1$ 个线段树并存 $26$ 个值。前者更为容易实现，后者更难实现，但可能有复杂度更优的做法。

### 树上二分

需要对线段树二分时，可以直接在线段树上做。线段树每深一层长度就减少一半，与二分类似，且可以利用已经过的节点的值 $O(1)$ 查询所需值。

### 前缀和特性

记 $a$ 前缀和序列为 $s$。

$a_i=s_{i-1}$ 时，$a_i$ 至少比 $a_{i-1}$ 翻了一倍。

一些最大值有关的东西也有类似的翻倍性质。

### 线段树，在查询时一些东西只能计算一次

先保存查询（强制在线需用主席树）。

从小到大枚举 $r$，此时加入了元素 $a_r$，加入 $a_r$ 后会重复的所有元素做修改（数量应较少），此时查询即可回答所有以 $r$ 为右端点的问题。

### 主席树（可持久化线段树）

保存了各个版本的线段树，一次修改是一个版本，有 $k$ 个版本则空间复杂度额外加 $O(k\log n)$。

每次修改时，只有 $\log n$ 个节点的值发生了变化，所以可以每次新建版本时建一个新的根，未变化的节点直接复用之前的节点，变化的再新建节点。

### 元素可修改次数极少的线段树

修改时将每个元素单点修改，记录还可以修改的元素，设修改次数为 $k$，复杂度 $O(nk\log n)$。

正在渲染内容...

Limit 的线段树题单 总结

Limit 的线段树题单总结