线段树与平衡树 - 洛谷保存站

# 线段树

## 核心要点：

线段树主要维护信息和标记。

对于以下操作若能够做到 $ O(k) $ 合并：

信息+信息；

标记+标记；

标记+信息；

那么线段树即可做到 $ O(n k \log n) $ 维护区间信息。

## 例题

### [P6327 区间加区间 sin 和](https://www.luogu.com.cn/problem/P6327)

套和差角公式即可，简单题。

时间复杂度 $ O((n + q) \log n) $。

### [P7706 「Wdsr-2.7」文文的摄影布置](https://www.luogu.com.cn/problem/P7706)

由于单点修改很容易做到 $ O(\log) $，所以我们只需要考虑如何合并区间信息就行了。

这题可以考虑和小白那题一样的策略，维护 $ ma, mb, lma, rma, tma $ 分别表示 $ a $ 的最大值， $ b $ 的最小值， $ \max_{i} \max_{j > i} a_i - b_j $，$ \max_{i} \max_{j < i} a_i - b_j $，和当前区间的答案。

容易得出以下转移方程：

$ ma = \max(L.ma, R.ma) $

$ mb = \min(L.mb, R.mb) $

$ lma = max(L.lma, R.lma, L.ma - R.mb) $

$ rma = max(L.rma, R.rma, R.ma - L.mb) $

$ tma = max(L.tma, R.tma, L.lma + R.ma, R.rma + L.ma) $

时间复杂度 $ O((n + q) \log n) $。

### [P4344 [SHOI2015] 脑洞治疗仪](https://www.luogu.com.cn/problem/P4344)

（傻逼题意，读了 $ 10 $ 分钟）

可以发现操作可以通过线段树二分转化为区间赋值。

时间复杂度 $ O((n + q) \log n) $。不会线段树二分可以写 $ O((n + q) \log^2 n) $，也能过。

### 无题号

题意：

给你一个长度为 $ n $ 的序列，有 $ m $ 个操作：

1: 单点修改；

2: 区间查询有没有重复的数字。

数据范围：$ 1 \leq n,m \leq 5 \times 10^5 $。

由于是单点修改，考虑没有修改的时候怎么做。

可以考虑维护每一个数字和后继 $ ne_i $ 满足 $ ne_i $ 是满足 $ a_i = a_{ne_i} $ 的最小的 $ ne_i $。

可以维护区间的最小后继 $ max_{ne} $，若 $ max_{ne} $ 小于等于区间的右边界，那么显然是有重复数字的。

至于单点修改，稍微分析一下会发现可以转换为多个单点修改，用 $ set $ 稍微维护一下就可以了。

时间复杂度 $ O((n + m) \log n) $。

### [区间最大公约数](https://www.luogu.com.cn/problem/U305764)

题意：

给你一个长度为 $ n $ 的序列，有 $ m $ 次操作：

1: 区间加

2: 求区间中所有数的最大公约数

数据范围：$ 1 \leq n,m \leq 10^5 $，$ 1 \leq a_i \leq 10^9 $。

考虑这样设计一个区间的信息，一个区间存储它的左端点 $ a_l $ 和 $ gcd(a_{l + 1} - a_{l}, a_{l + 2} - a_{l + 1}, \cdots, a_[r] - a_{r - 1}) $。

这样，原本是区间加的修改就变成的单点修改！

而显然，一段区间的 $ gcd $ 就是 $ \gcd(a_l, x) $！

合并区间是显然的。

时间复杂度 $ O((n + m) \log n \log V) $，其中 $ V $ 是值域。

### [P5278 算术天才⑨与等差数列](https://www.luogu.com.cn/problem/P5278)

很显然，只要满足以下条件即可：

1: 最大值减最小值要满足条件

2: 数互不重复

3: 差分数字的 $ gcd $ 为 $ k $

用上面讲的知识维护就可以了。

时间复杂度 $ O((n + m) \log n \log V) $。

### [P6617 查找 Search](https://www.luogu.com.cn/problem/P6617)

和前面有一题一样，维护前驱后继即可。

可以用支配优化，每次后继只记录最接近的。

时间复杂度 $ O((n + q) \log n) $。

# 势能线段树/颜色均摊

## 例题

### [P4145 上帝造题的七分钟 2 / 花神游历各国](https://www.luogu.com.cn/problem/P4145)

势能线段树模版题。

时间复杂度 $ O(n \times \log n \times \log \log V) $。

### [CF438D The Child and Sequence](https://www.luogu.com.cn/problem/CF438D)

取模 = 除以2

时间复杂度 $ O((n + q) \times \log n \log V) $。

### [P9989 Ynoi Easy Round 2023 TEST_69](https://www.luogu.com.cn/problem/P9989)

显然，一个数最多被 gcd $ O(log) $ 次就会变成 $ 1 $。

所以若一个区间的 lcm 是 x 的因数，那么这个区间就不用被 gcd，否则肯定有一个数要被 gcd。

稍微分析一下可以额发现时间复杂度为 $ O(n \log n \log V) $。

记得开 ` __int128 `。

### [Naive Operations](https://vjudge.net/problem/HDU-6315)

妙妙题。

首先考虑，对于一个坐标 $ i $，至少要加多少次 $ a_i $，才能使得 $ [\frac{a_i}{b_i}] $ 加 $ 1 $？

容易发现，只需要加 $ \frac{1}{b_i} $ 次即可。

那么最坏情况下，$ \frac{a}{b} $ 会被加 $ m \times \sum_{i = 1}^n \frac{1}{n} = m \log n $ 次。

所以考虑用一个线段树维护 $ b - a $ 的最小值即其坐标，另一个线段树维护 $ [\frac{a}{b}] $。若存在 $ i $ 使得 $ b_i - a_i = 0 $，那么 $ [\frac{a_i}{b_i}] \leftarrow [\frac{a_i}{b_i}] + 1 $，然后 $ b_i - a_i \leftarrow b_i $。

时间复杂度 $ O((n + m) \log n \log n) $。

### [ZQC 的手办](https://loj.ac/p/504)

考虑如何求出一个区间的前 $ k $ 小，可以发现以下策略：

先求出第一小和它的坐标，然后设为 $ \inf $，然后在求出第二小和它的坐标，然后设为 $ \inf $ $ \cdots $

这样可以在 $ O(x \log n) $ 的时间复杂度内求出前 $ x $ 小。

至于区间 $ max $ 可以标记永久化解决。

时间复杂度 $ O(\sum x \log n) $。

### [CF280D k-Maximum Subsequence Sum](https://www.luogu.com.cn/problem/CF280D)

两种做法：

法1：闵可夫斯基和（$ O(n k \log n) $，略）

法2：反悔贪心。

选一个最大连续字段和，然后将选的区间全部乘上 $ -1 $。

证明需要模拟费用流。

时间复杂度 $ O(n k \log n) $。

### [CF444C DZY Loves Colors](https://www.luogu.com.cn/problem/CF444C)

又是势能线段树模版题/颜色均摊模版题。

可以发现相邻点的颜色会越来越相似，所以可以记录一个区间的颜色是否相同。若相同直接区间修改打标记即可。

时间复杂度 $ O((n + m) \log n) $。

### [CF1638E Colorful Operations](https://www.luogu.com.cn/problem/CF1638E)

打 lazytag 来延迟区间加即可。

用势能线段树和颜色均摊模型都可以做。

时间复杂度 $ O((n + q) \log n) $。

### [CF453E Little Pony and Lord Tirek](https://codeforces.com/problemset/problem/453/E)

设一段颜色代表这段区间上一次推平的时间是相同的。

对于一段颜色用主席树即可。

时间复杂度 $ O((n + m) \log n) $。

正在渲染内容...