作者：Adimn

[ 数据结构 ] [ # ] 线段树

8个月前 ⋅ 0

简介

线段树是一组用来维护区间信息的数据结构，可以用来实现单点查询和区间查询。

主要包括以下五种基本操作：

build：建树

采用递归建树，直至叶子结点。

query：区间查询

根据查询区间 [l, r]，和当前区间 [l', r'] 的重叠范围，决定下一次递归区间。直到 l < l' < r' < r，此时返回 [l', r'] 的值即可。
最坏情况是 O( 4 * logN )

pushup：根据子节点信息，更新当前节点信息。

例如：求区间最大值，表示从左节点和右节点中选出最大值，赋值给当前节点。

modify：单点修改

首先，通过二分，查找 [x, x] 区间所对应的叶子结点。然后，自底向上，更新父节点区间最大值。

在区间修改时，通过延迟对节点信息的更改，从而减少可能不必要的操作次数。