线段树type
status
date
slug
summary
tags
category
icon
password
Property
线段树（Segment Tree）：一种基于分治思想的二叉树，用于在区间上进行信息统计。它的每一个节点都对应一个区间
[left, right] ，left、right 通常是整数。每一个叶子节点表示了一个单位区间（长度为 1），叶子节点对应区间上 left == right。每一个非叶子节点 [left, right] 的左子节点表示的区间都为 [left, (left + right) / 2]，右子节点表示的的区间都为 [(left + right) / 2 + 1, right]。线段树是一棵平衡二叉树，树上的每个节点维护一个区间。根节点维护的是整个区间，每个节点维护的是父亲节点的区间二等分之后的其中一个子区间。当有个元素时，对区间的操作（单点更新、区间更新、区间查询等）可以在 的时间复杂度内完成。
一棵区间为
[0, 7] 的线段树：
线段树的特点：
- 线段树的每个节点都代表一个区间
- 线段树具有唯一的根节点，代表的区间是整个统计范围，比如
[1, n]。
- 线段树的每个叶子节点都代表一个长度为
1的单位区间[x, x]。
- 对于每个内部节点
[left, right]，它的左子节点是[left, mid]，右子节点是[mid + 1, right]。其中mid = (left + right) / 2（向下取整）。
线段树的常见题型
RMQ 问题 ：Range Maximum / Minimum Query 的缩写，对于长度为n的数组序列 nums，回答若干个询问问题
RMQ(nums, q_left, q_right)，要求返回数组序列nums在区间[q_left, q_right]中的最大（最小）值。也就是求区间最大（最小）值问题。假设查询次数为
q，则使用朴素算法解决 RMQ 问题的时间复杂度为。而使用线段树解决 RMQ 问题的时间复杂度为~ 之间。
单点更新，区间查询问题
- 修改某一个元素的值
- 查询区间为
[q_left, q_right]的区间值
这类问题直接使用「线段树的单点更新」和「线段树的区间查询」即可解决
区间更新，区间查询问题
- 修改某一个区间的值
- 查询区间为
[q_left, q_right]的区间值
这类问题直接使用「线段树的区间更新」和「线段树的区间查询」即可解决
区间合并问题
- 修改某一个区间的值
- 查询区间为
[q_left, q_right]中满足条件的连续最长区间值
这类问题需要在「线段树的区间更新」和「线段树的区间查询」的基础上增加变动，在进行向上更新时需要对左右子节点的区间进行合并。
扫描线问题
虚拟扫描线或扫描面来解决欧几里德空间中的各种问题，一般被用来解决图形面积，周长等问题。
主要思想为：想象一条线（通常是一条垂直线）在平面上扫过或移动，在某些点停止。几何操作仅限于几何对象，无论何时停止，它们都与扫描线相交或紧邻扫描线，并且一旦线穿过所有对象，就可以获得完整的解。
这类问题通常坐标跨度很大，需要先对每条扫描线的坐标进行离散化处理，将
y 坐标映射到 0, 1, 2, ... 中。然后将每条竖线的端点作为区间范围，使用线段树存储每条竖线的信息（x 坐标、是左竖线还是右竖线等），然后再进行区间合并，并统计相关信息。动态开点线段树
在有些情况下，线段树需要维护的区间很大（例如），在实际中用到的节点却很少。如果使用之前数组形式实现线段树，则需要大小的空间，空间消耗有点过大了。
这时候就可以使用动态开点的思想来构建线段树。
动态开点线段树的算法思想如下：
- 开始时只建立一个根节点，代表整个区间
- 当需要访问线段树的某棵子树（某个子区间）时，再建立代表这个子区间的节点