数据结构和区间类问题

-1 前言

一次课上的浅谈，随听随记。

0 概述

1 各类数据结构

1.1 线段树

线段树，顾名思义，每个节点都代表一个区间。

从原序列建树，然后按照 $[l,r]$ 到 $[l,mid]$ 和 $[mid+1,r]$ 来划分。

叶子节点是长度为1的区间。

一颗维护长度 $N$ 的序列的线段树总有 $2N-1$ 个节点，$\text{log} n$ 层。

不用动态开点的情况下，维护长度为 $N$ 的序列的线段树的数组需要开到大于 $N$ 的第二个 $k\in \mathbb{N^+},2^k$ 形式的整数。

线段树主要维护区间问题，可以支持区间和单点的修改和查询。

一个证明：线段树的每次区间操作总能把查询区间分成 $\text{log}n$ 级别个线段树上节点，也就是 线段树取件操作复杂度的证明。

考虑原序列的查询区间，在进行一次划分后可能对于当前线段树区间有三种情况：

• 完全在左子区间

• 完全在右子区间

• 跨越中间，即左右两边都有

考虑前两种情况在继续划分不超过 $\text{log}n$ 次也会成为第三种情况，或者从叶子节点返回。因此我们只考虑第三种。

对于第三种，还有三种情况：

• 查询区间是当前线段树区间的一个前缀

• 查询区间是当前线段树区间的一个后缀

• 查询区间是当前线段树区间的一个子区间

第一种情况，我们递归到左子区间后会立即返回，因为完全包含。第二种情况同理。

第三种，在继续递归不超过 $\text{log}n$ 次后也会成为前两种情况，因此总的划分节点数量是 $\text{log}n$ 级别。

懒标记？待补。

1.1.2 动态开点和线段树合并

动态开点的思想就是随用随建随取，对于没有用到的节点就不开了。

和普通的线段树差别不大，主要在于更加省空间以及一些特殊功能（如主席树或者更高级的线段树算法）。

假如有很多动态开点线段树维护一个序列，每个线段树维护序列的一个性质，最后需要把若干个线段树合并起来，这就是线段树合并。

考虑具体实现。

我们考虑对于两个线段树上相同位置的节点 $p$ 和 $q$ ，那么：

• 如果 $p$ 和 $q$ 都存在，按照规则合并到 $p$（这里假设合并后的节点是$p$，即删除 $q$）。

• 如果其中一个不存在，那么返回存在的那一个。

整体时间复杂度 $O(m\text{log}n)$ ，证明待补。

1.1.3 可持久化线段树

有些题目中需要我们在修改操作同时还要查询历史版本信息，我们就需要可持久化线段树。

可持久化线段树的思想就是大部分节点可以复用，由于每次修改更改了不超过 $\text{log}n$ 个节点，那么我们可以每次修改后动态开点，新开的点的连向原来的边。

？？？

剩下的等以后待补

1.1.4 线段树的更复杂维护信息

待补

线段树维护分治信息略解 - 博客 - _rqy的博客