分段树（Segment Tree）
1st revision - 2024-12-15
更常见的名字是线段树，但我认为“线段” 的翻译雅而不达、语义失焦1，不如“分段”平白直意。
本文基本算是对 cp-algorithms - Segment Tree 的一个 Rust 实现版本的介绍。
基础概念
分段树是用来解决数组上区间查询问题的数据结构。
它把数组代表的区间不断二分，直到区间小到只含有单个元素，把它们用二叉树的结构组织起来，顶点代表整个区间，它的左孩子和右孩子分别代表整个区间的左右两半，以此类推，直到叶子节点。
如原文这里所示。
它非常好地体现了分治2思想，有了这样的数据结构后，当面对一个区间查询时，只需要在从根到叶子对树递归时把已有的局部区间的答案进行组合，就能得到最终答案。
查询的复杂度
可以证明查询过程中每一层最多访问 $4$ 个节点。
使用归纳法证明，初始条件是一个节点，符合。
假设上一层访问不超过 $4$ 个节点：
- 如果上一层只访问了两个或更少的节点，那么这一层最多访问 $4$ 个；
- 如果上一层访问 $3$ 个或 $4$ 个节点，由于访问的区间是连续的，中间部分正好对应分段树的区间，会直接返回，因此只有边缘的左右两个节点可能会向下访问，这一层仍然最多访问 $4$ 个
证毕。
因此查询的时间复杂度由树高决定，是 $O(\text{log}n)$ 。
实现前瞻
作为树型结构自然就有数组和指针两种实现，而分段树可以很容易地使用数组实现3，这让它看起来非常靠谱！
接下来我们主要讨论的就是线段树的数组实现。
树的布局
我们首先想到的就是水平布局，也就是按照完全二叉树的结构，依次放置每一层的节点，我们可以称之为 BFS 型布局。
BFS 型
BFS 型有一个很好的性质就是计算节点的左右孩子的位置非常简单，如果我们的数组编号从 $1$ 开始，那么根据完全二叉树的性质， $t[i]$ 节点的左孩子和右孩子分别为 $t[2\cdot i]$ 和 $t[2\cdot i+1]$ 。
可以很容易地证明这一点：
首先，已知高度为 $h$ 的满的完全二叉树有 $2^h - 1$ 个节点4，高度为 $h$ 的层有 $2^{h-1}$ 个节点。
假设 $t[i]$ 节点在树的 $h$ 层，同一层的前面包括它在内，有 $x$ 个节点，后面有 $y$ 个节点，那么显然有:
\[\begin{array}{l} i &= 2^{h-1} - 1 + x &\quad(1)\\ x+y &= 2^{h-1} &\quad (2)\\ \end{array}\]而它与左孩子的距离 $d$ 有 $d=y+2(x-1)+1$ ，利用 $(2)$ 式消解掉 $y$ ，得到 $d=2^{h-1} + x - 1 = i$ ，也就是 $t[i]$ 节点的左孩子距离为 $i$ ，右孩子紧邻左孩子，距离为 $i+1$ ，证毕。
如果我们的编号不从 1 开始，而是从 0 开始，那么有 $i’ = i-1$ ，带入 ${\large i_{\text{left}}} = 2i$ ，有 ${\large i ’_{\text{left}}}+1=2(i’+1)$ ，于是：
\[\begin{array}{l} {\large i ’_{\text{left}}} &=2i'+1\\ {\large i ’_{\text{right}}} &=2i’+2 \end{array}\]需要指出的是，虽然我们按照完全二叉树的结构排列节点，但分段树本身并不一定是完全二叉树，最后一层的节点并不是规律地从左开始分布5，而是按照本身的奇偶性规律排布，比如考虑 $6$ 个元素的分段树：$(6)-(3, 3)-(2, 1, 2, 1)$ 。
按照水平布局，分段树数组需要的节点数按照满的完全二叉树来进行分配，也就是 $2^h -1 = 2^{\lceil \text{log}_2 n \rceil} - 1 < 2^{\lceil \text{log}_2 n\rceil} \leqslant 4n$ ，因此即使以 $1$ 为基，也只需要分配 $4n$ 大小的空间。
DFS 型
仔细考虑一下分段树的形状，发现它准确说应该是一棵满二叉树（full binary tree），而满二叉树有这样的性质，就是如果叶子节点数为 $i$ ，那么中间节点数就是 $i-1$ ，整棵树的节点数就是 $2\cdot i-1$ 。
这个性质不需要特别证明，它直接就是定义给出的：满二叉树的直接定义是节点要么没有孩子，要么有两个孩子，但它还有一个递归定义：
- 单节点是满二叉树；
- 根的两个孩子都是满二叉树的二叉树是满二叉树
这个递归定义也就是我们归纳推理的过程：
- 单节点的时候，叶子节点比中间节点数多 $1$ ；
- 假设根的两个孩子都是满二叉树，那么左右孩子上的叶子节点数之和比中间结点数之和多 $2$ ，加上作为中间节点的根节点，于是整棵树的叶子节点仍然比中间节点多 $1$
证毕。
根据满二叉树这个性质，我们可以发现，为长度为 $n$ 的数组建立的分段树确定地含有 $2n-1$ 个节点 ，这么一看，BFS 型申请的 $4n$ 的空间实在有些浪费，于是有了内存节省布局的 DFS 型。
DFS 顾名思义是垂直布局，放置根节点后，先放置整棵左树，再放置整棵右树。不过单纯地垂直布局并不会节省空间，真正关键的是在垂直分布中，我们使用了满二叉树的布局而不是完全二叉树的布局，这是因为在树上遍历的过程中，我们知道节点所代表的范围区间，也就是节点所代表的子树的叶子节点数，因此我们可以预知整棵子树的大小。
这样我们就可以直接计算出左右孩子的位置，对节点 $t[i]$ ，设左孩子对应区间长度为 $l$ ，则它的左右孩子分别为 $t[i+1]$ 和 $t[i+2\cdot l-1 + 1]=t[i+2\cdot l]$ 。
这样即使仍然基 $1$ ，也只需要申请 $2n$ 大小的空间，比起 BFS 型整整节省了一半的空间！
全面地比较这两型布局：
时间性能上，由于我们的访问是逐层进行的，BFS 的分层布局使得左右两个孩子紧邻，有更好地局部性，但毕竟仍然是在同一个数组上访问，差距也大不到哪儿去，事实上经过一个简单测试，发现两型的性能几乎没有区别；
空间性能上，DFS 型完胜，BFS double 了空间占用，太差了；
易用性上，BFS 是普通人都能想到的，左右孩子的位置也很简单，不过 DFS 型经过我的讲解也是非常的简单易懂，两者没有明显差别。
综合以上比较，更推荐 DFS 型作为默认地数组上的默认布局。
范式的描述
我们尝试尽量用 Rust 的抽象机制把本篇涉及的所有概念这些可选项揉到一起。
存储布局和树上游标
存储布局指得是存储的数组大小以及树上位置与数组位置的对应关系，通过存储布局和树上游标就可以建立对分段树的索引方法。
pub trait TreeLayout: private::Sealed {
fn left(i: usize, t: TreeCursor) -> usize;
fn right(i: usize, t: TreeCursor) -> usize;
fn root() -> usize {
1
}
fn size(cap: usize) -> usize;
}
impl TreeLayout for BFS {
fn left(i: usize, _t: TreeCursor) -> usize {
i * 2
}
fn right(i: usize, _t: TreeCursor) -> usize {
i * 2 + 1
}
fn size(cap: usize) -> usize {
4 * cap
}
}
impl TreeLayout for DFS {
fn left(i: usize, _t: TreeCursor) -> usize {
i + 1
}
fn right(i: usize, t: TreeCursor) -> usize {
// i + 2(n(left))
i + 2 * ((t.tl + t.tr) / 2 - t.tl + 1)
}
fn size(cap: usize) -> usize {
2 * cap - 1 + 1
}
}
mod private {
pub trait Sealed {}
impl Sealed for super::BFS {}
impl Sealed for super::DFS {}
}
impl TreeCursor {
fn root(raw_len: usize) -> Self {
debug_assert!(raw_len > 0);
Self {
tl: 0,
tr: raw_len - 1,
}
}
fn is_end(&self) -> bool {
self.tl == self.tr
}
fn is_matched(&self, (l, r): (usize, usize)) -> bool {
self.tl == l && self.tr == r
}
fn left(&self) -> Self {
Self {
tl: self.tl,
tr: (self.tl + self.tr) / 2,
}
}
fn right(&self) -> Self {
Self {
tl: (self.tl + self.tr) / 2 + 1,
tr: self.tr,
}
}
}
这里使用了继承私有模块的公共 Trait 来封装暴露给下游的公共 Trait 的技巧，因为我们定义并暴露出 TreeLayout 只是为了允许用户自由选择他们需要的分段树布局，而并不期望用户实现它。
抽象机制的实现
分段树本身只是一个数据结构，用来解决区间更新和查询的问题，为了灵活地适配针对具体问题的解决算法，需要提供一个合适的抽象机制，这里面主要的麻烦是需要一个获取相当于幺半群里单位元的操作，以供构建和查询时使用。
可以自己定义一个 trait 来规定这个操作，但是如果要为每个类型去实现这个 trait ，就要额外增加抽象层次。
于是考虑运用 Rust 既有 trait 来满足要求，而一个偶然的机会，我发现 Iterator<Item = T>.sum 返回一个确定的值 T 而不是我自己预计的 Option<T> ，这让我很诧异，去看了 Sum trait 的实现，发现它默认了一个返回对于，比如加法，单位元的操作，于是直接使用 Sum 配合 Add, AddAssign 就可以定义出我们需要的对问题的抽象。
macro_rules! zero {
() => {
[].into_iter().sum()
};
}
pub struct SegmentTree<T, L = DFS> {
data: Vec<T>,
root: TreeCursor,
_marker: PhantomData<L>,
}
impl<T, L> SegmentTree<T, L>
where
L: TreeLayout,
T: Sum + Clone + Add<Output = T>,
for<'a> &'a T: Add<&'a T, Output = T>
{
// ...
}
构建和查询
尝试划分按照分段树的区间进行划分，直到一个错误的区间范围，这时直接返回“单位元”，比起检查返回值要简洁很多
// impl SegmentTree<T, L>
pub fn new<U: Clone + Into<T>>(raw: &[U]) -> Self {
assert!(!raw.is_empty());
let mut data = vec![zero!(); L::size(raw.len())];
let root = TreeCursor::root(raw.len());
Self::build(&mut data, raw, L::root(), root);
Self {
data,
root,
_marker: PhantomData::<L>,
}
}
fn build<U: Clone + Into<T>>(
data: &mut [T],
arr: &[U],
i: usize,
t: TreeCursor,
) {
if t.is_end() {
data[i] = arr[t.tl].clone().into();
} else {
Self::build(data, arr, L::left(i, t), t.left());
Self::build(data, arr, L::right(i, t), t.right());
data[i] = &data[L::left(i, t)] + &data[L::right(i, t)];
}
}
pub fn query<R: RangeBounds<usize>>(&self, range: R) -> T {
let Range { start, end } = std::slice::range(range, ..self.root.tr + 1);
self.query_((start, end - 1), L::root(), self.root)
}
fn query_(&self, (l, r): (usize, usize), i: usize, t: TreeCursor) -> T {
if l > r {
return zero!();
}
if t.is_matched((l, r)) {
self[i].clone()
} else {
let lf =
self.query_((l, min(t.left().tr, r)), L::left(i, t), t.left());
let rh = self.query_(
(max(t.right().tl, l), r),
L::right(i, t),
t.right(),
);
lf + rh
}
}
// ...
单点更新
如果原数组的某个值发生了更新，那么对应地，从分段树的根一直到该值所在的叶子，整条路径也需要更新，而这个过程和构建与查询的过程是同构的。
// impl SegmentTree<T, L>
pub fn assoc(&mut self, i: usize, new_val: T) {
assert!(i <= self.root.tr);
self.assoc_(L::root(), self.root, i, new_val)
}
fn assoc_(&mut self, i: usize, t: TreeCursor, ti: usize, new_val: T) {
if t.is_end() {
self.data[i] = new_val;
} else {
let lfi = L::left(i, t);
let rhi = L::right(i, t);
if ti <= t.left().tr {
self.assoc_(lfi, t.left(), ti, new_val);
} else {
self.assoc_(rhi, t.right(), ti, new_val);
}
self.data[i] = &self.data[lfi] + &self.data[rhi];
}
}
// ...
经典问题
我们将会层层递进地介绍一些适用于上述分段树范式的经典问题。
简单单值
从简单到复杂，我们举三个例子来说明具体的使用方法。
区间和
这是分段树最原始的例子，什么都不用做，直接构建和查询即可。
区间最大值
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
#[repr(transparent)]
pub struct RangeMax<T>(T);
impl<T> From<T> for RangeMax<T> {
fn from(value: T) -> Self {
Self(value)
}
}
impl<T: Sum + Ord> Sum for RangeMax<T> {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
Self(iter.map(|x| x.0).max().unwrap_or(zero!()))
}
}
impl<T: Ord> Add for RangeMax<T> {
type Output = Self;
fn add(self, rhs: Self) -> Self::Output {
Self(std::cmp::max(self.0, rhs.0))
}
}
impl<'a, T: Ord + Clone + 'a> Add for &'a RangeMax<T> {
type Output = RangeMax<T>;
fn add(self, rhs: Self) -> Self::Output {
RangeMax(std::cmp::max(&self.0, &rhs.0).clone())
}
}
impl<'a, T: Ord + Clone> AddAssign<&'a Self> for RangeMax<T> {
fn add_assign(&mut self, rhs: &'a Self) {
if rhs > self {
*self = rhs.clone();
}
}
}
impl<T: Ord> PartialEq<T> for RangeMax<T> {
fn eq(&self, other: &T) -> bool {
self.0.eq(other)
}
}
impl<T: Ord> PartialOrd<T> for RangeMax<T> {
fn partial_cmp(&self, other: &T) -> Option<Ordering> {
self.0.partial_cmp(other)
}
}
最大公约数
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[repr(transparent)]
pub struct RangeGCD<T>(T);
impl<T> From<T> for RangeGCD<T> {
fn from(value: T) -> Self {
Self(value)
}
}
macro_rules! impl_range_gcd {
($($ty:ty),*) => {
$(
impl Sum<Self> for RangeGCD<$ty> {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.reduce(|acc, x| acc + x).unwrap_or(Self(0))
}
}
impl Add<Self> for RangeGCD<$ty> {
type Output = Self;
fn add(self, rhs: Self) -> Self::Output {
Self(gcd!(self.0, rhs.0))
}
}
impl<'a> Add<Self> for &'a RangeGCD<$ty> {
type Output = RangeGCD<$ty>;
fn add(self, rhs: Self) -> Self::Output {
RangeGCD(gcd!(self.0, rhs.0))
}
}
impl<'a> AddAssign<&'a Self> for RangeGCD<$ty> {
fn add_assign(&mut self, rhs: &'a Self) {
self.0 = gcd!(self.0, rhs.0)
}
}
)*
};
}
impl_range_gcd!(i32, i64, usize);
复合类型
统计给定区间的最大值和出现次数。
/// (max value, max value count)
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct RangeMaxStats<T> {
val: T,
cnt: usize,
}
impl<T> From<T> for RangeMaxStats<T> {
fn from(value: T) -> Self {
Self { val: value, cnt: 1 }
}
}
impl<T> From<(T, usize)> for RangeMaxStats<T> {
fn from(value: (T, usize)) -> Self {
Self {
val: value.0,
cnt: value.1,
}
}
}
impl<T: Sum + Ord + Clone + Default> Sum for RangeMaxStats<T> {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.reduce(|acc, x| acc + x).unwrap_or(Self {
val: T::default(),
cnt: 0,
})
}
}
impl<T: Ord + Clone> Add<Self> for RangeMaxStats<T> {
type Output = Self;
fn add(self, rhs: Self) -> Self::Output {
match self.val.cmp(&rhs.val) {
Less => rhs,
Equal => RangeMaxStats {
val: rhs.val,
cnt: self.cnt + rhs.cnt,
},
Greater => self,
}
}
}
impl<'a, T: Ord + Clone> Add<Self> for &'a RangeMaxStats<T> {
type Output = RangeMaxStats<T>;
fn add(self, rhs: Self) -> Self::Output {
match self.val.cmp(&rhs.val) {
Less => rhs.clone(),
Equal => RangeMaxStats {
val: self.val.clone(),
cnt: self.cnt + rhs.cnt,
},
Greater => self.clone(),
}
}
}
impl<'a, T: Ord + Clone> AddAssign<&'a Self> for RangeMaxStats<T> {
fn add_assign(&mut self, rhs: &'a Self) {
match self.val.cmp(&rhs.val) {
Less => *self = rhs.clone(),
Equal => self.cnt += rhs.cnt,
Greater => (),
};
}
}
排名位置
比如，统计 $0$ 的个数，并查找第 $k$ 个 $0$ 的位置
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
#[repr(transparent)]
pub struct RangeZeroStats<T> {
cnt: usize,
_marker: PhantomData<T>,
}
impl<T: Sum + Eq> From<T> for RangeZeroStats<T> {
fn from(value: T) -> Self {
Self {
cnt: if value == zero!() { 1 } else { 0 },
_marker: PhantomData,
}
}
}
impl<T: Sum + Eq> Sum for RangeZeroStats<T> {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.reduce(|acc, x| acc + x).unwrap_or(RangeZeroStats {
cnt: 0,
_marker: PhantomData,
})
}
}
impl<T> Add<Self> for RangeZeroStats<T> {
type Output = Self;
fn add(self, rhs: Self) -> Self::Output {
Self {
cnt: self.cnt + rhs.cnt,
_marker: PhantomData,
}
}
}
impl<'a, T> Add<Self> for &'a RangeZeroStats<T> {
type Output = RangeZeroStats<T>;
fn add(self, rhs: Self) -> Self::Output {
RangeZeroStats {
cnt: self.cnt + rhs.cnt,
_marker: PhantomData,
}
}
}
impl<'a, T> AddAssign<&'a Self> for RangeZeroStats<T> {
fn add_assign(&mut self, rhs: &'a Self) {
self.cnt += rhs.cnt
}
}
在具体 trait 上实现的查询方法。
impl<T> RangeZeroStats<T>
where
for<'a> &'a T: Add<&'a T, Output = T> + Sub<&'a T, Output = T> + Ord + 'a,
for<'a> T: 'a,
{
pub fn find_nth<L: TreeLayout>(
tree: &SegmentTree<RangeZeroStats<T>, L>,
n: usize,
) -> Option<usize> {
if n + 1 > tree[L::root()].cnt {
None
} else {
Some(Self::find_nth_(tree, n, L::root(), tree.root))
}
}
fn find_nth_<L: TreeLayout>(
tree: &SegmentTree<RangeZeroStats<T>, L>,
n: usize,
i: usize,
t: TreeCursor,
) -> usize {
if t.is_end() {
t.tl
} else {
if tree[L::left(i, t)].cnt > n {
Self::find_nth_(tree, n, L::left(i, t), t.left())
} else {
Self::find_nth_(
tree,
n - tree[L::left(i, t)].cnt,
L::right(i, t),
t.right(),
)
}
}
}
}
impl<T> Into<usize> for RangeZeroStats<T> {
fn into(self) -> usize {
self.cnt
}
}
impl<'a, T> Sub<Self> for &'a RangeZeroStats<T> {
type Output = RangeZeroStats<T>;
fn sub(self, rhs: Self) -> Self::Output {
RangeZeroStats {
cnt: self.cnt - rhs.cnt,
_marker: PhantomData,
}
}
}
类似地还有查找给定区间里的元素位置，使得它的前缀和不小于给定值。
FindFirst
查找给定区间里第一个符合条件的元素的位置。
比如，查找给定区间里第一个严格大于给定值的值的位置。
首先构建一个统计最大值的分段树，前面已经构建好了，这里是查询方法。
impl<T> RangeMax<T>
where
T: Ord,
for<'a> &'a T: Add<&'a T, Output = T> + 'a,
for<'a> T: 'a,
{
pub fn query_first_gt<L: TreeLayout, R: RangeBounds<usize>>(
tree: &SegmentTree<Self, L>,
range: R,
x: &Self,
) -> Option<usize> {
let Range { start, end } = std::slice::range(range, ..tree.len());
Self::query_first_gt_1(tree, x, (start, end - 1), L::root(), tree.root)
}
fn query_first_gt_1<L: TreeLayout>(
tree: &SegmentTree<Self, L>,
x: &Self,
(l, r): (usize, usize),
i: usize,
t: TreeCursor,
) -> Option<usize> {
// left or right
if t.tl > r || t.tr < l {
None
}
// inner
else if t.tr <= r && t.tl >= l {
Self::query_first_gt_2(tree, x, i, t)
}
// cross
else {
// avoid bound overflow
let left_res = Self::query_first_gt_1(
tree,
x,
(l, r),
L::left(i, t),
t.left(),
);
if left_res.is_some() {
return left_res;
}
Self::query_first_gt_1(tree, x, (l, r), L::right(i, t), t.right())
}
}
fn query_first_gt_2<L: TreeLayout>(
tree: &SegmentTree<Self, L>,
x: &Self,
i: usize,
t: TreeCursor,
) -> Option<usize> {
if &tree[i] <= x {
return None;
}
if t.is_end() {
Some(t.tl)
} else {
if &tree[L::left(i, t)] > x {
Self::query_first_gt_2(tree, x, L::left(i, t), t.left())
} else {
Self::query_first_gt_2(tree, x, L::right(i, t), t.right())
}
}
}
}
最大和的子分段
这是一个特定的，但是复杂的问题：查找给定区间范围内的一个子区间，使得有区间里所有元素之和最大。
解决这个问题的构思还是比较巧妙的，利用一个复杂的统计结构，分而治之地分而治之，这个结构包含 4 个成员：
- pref，最大前缀和；
- suff，最大后缀和；
- sum，区间元素之和；
- ans，区间答案，也就是最大的子区间和
区间答案就是由三个后选值：
- 左区间的答案；
- 右区间的答案；
- 左区间最大后缀和 + 右区间最大前缀和
#[derive(Clone, Copy, Debug, Default)]
pub struct SubSegMaxSumStats<T> {
/// total sum of the segment
pub sum: T,
/// max prefix sum
pub pref: T,
/// max suffix sum
pub suff: T,
/// query answer of max sum of the segment
pub ans: T,
}
impl<T: Number> From<T> for SubSegMaxSumStats<T> {
fn from(value: T) -> Self {
Self {
sum: value,
pref: value,
suff: value,
ans: value,
}
}
}
impl<T: Sum> Default for SubSegMaxSumStats<T> {
fn default() -> Self {
Self {
sum: zero!(),
pref: zero!(),
suff: zero!(),
ans: zero!(),
}
}
}
impl<T: Number> Sum for SubSegMaxSumStats<T> {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.reduce(|acc, x| acc + x).unwrap_or_default()
}
}
impl<T: Number> Add<Self> for SubSegMaxSumStats<T> {
type Output = Self;
fn add(self, rhs: Self) -> Self::Output {
let limit_ans = Self::default().ans;
if self.ans == limit_ans {
return rhs;
} else if rhs.ans == limit_ans {
return self;
}
Self {
sum: self.sum + rhs.sum,
pref: max(self.pref, self.sum + rhs.pref),
suff: max(self.suff + rhs.sum, rhs.suff),
ans: [self.ans, rhs.ans, (self.suff + rhs.pref)]
.into_iter()
.max()
.unwrap(),
}
}
}
impl<'a, T: Number> Add<Self> for &'a SubSegMaxSumStats<T> {
type Output = SubSegMaxSumStats<T>;
fn add(self, rhs: Self) -> Self::Output {
*self + *rhs
}
}
需要注意得是因为负数的存在，零不能当做这里的默认值，需要取一个足够小的负数，但也要注意数据类型越界的问题。
保存整个子数组
有一种分段树是在每个点上保存原数组对应区间里的所有值。
如果保存的子数组是用有序向量存储的，那么这个分段树实际上是在空间上还原了归并排序的整个过程，因此它也可以叫做 “Merge Sort Tree” ，可以在上面执行一系列查询的操作。
存储有序向量对原数组的元素修改时成本较高，可以改为经典的以 TreeMap 为基础的 multiset 6，
FindFirst
分段树本身的查询复杂度是 $O(\text{log}n)$ ，有序向量或者 multiset 上查询的时间复杂度也是 $O(\text{log}n)$ ，因此总的时间复杂度是 $O(\text{log}^2n)$ 。
分片级联
可以考虑使用 分片级联 的思想来加速对 findfirst 问题查询的过程。
这样的话，在树的构建过程中，不只是存储整个子数组，而是分片级联里面的 $M$ 列表，区别是原来是级联下一级，所以存储下一级的索引，而现在要级联左右孩子，需要存储左右孩子上的索引。
另外，由于需要保存整个子数组，所以只级联，不分片7 。
于是查询的过程就变为，在根节点上进行一次二分查找，然后做最多树高度的拉链。
以 $3$ 倍的空间为代价，让查询的时间复杂度降到了 $O(\text{log}n)$ 。
区间更新
分段树支持一种在给定区间上快速地批量更新元素8的方法。
这个区间更新的方法利用了“惰性更新”的思想，不妨以 update-add ，也就是批量增加一个固定值为例：
惰性方法9
在更新的时候，只更新到给定区间覆盖到的分段树上的区间。
比如对于分段树 $t[0..7]$ ，更新区间 $[3..7]$ ，则惰性更新的路径为：
\[\begin{array}{l} t[0..7] & \rightarrow [0..3] \rightarrow [2..3] \rightarrow [3]\\ & \rightarrow [4..7] \end{array}\]这就需要在分段树的区间上额外存储惰性更新的值，为了不影响既有结构，我们用额外的一个辅助数组来存储它：
#[repr(transparent)]
pub struct UpdaterAdd<T, L>(Vec<T>, PhantomData<L>);
impl<T, L> SegmentTree<T, L> {
/// Create an batch add updater
pub fn create_updater(&self) -> UpdaterAdd<T, L> {
UpdaterAdd(vec![zero!(); self.data.len()], PhantomData)
}
}
impl<T, L, I: SliceIndex<[T]>> Index<I> for UpdaterAdd<T, L> {
type Output = I::Output;
fn index(&self, index: I) -> &Self::Output {
&self.0[index]
}
}
impl<T, L, I: SliceIndex<[T]>> IndexMut<I> for UpdaterAdd<T, L> {
fn index_mut(&mut self, index: I) -> &mut Self::Output {
&mut self.0[index]
}
}
惰性更新的过程与一般的分段树的查询过程一样：
impl<T, L: TreeLayout> UpdaterAdd<T, L>
where
T: Clone + Sum + Add<Output = T> + Ord,
for<'a> T: AddAssign<&'a T>,
for<'a> &'a T: Add<&'a T, Output = T>,
{
pub fn assoc<R: RangeBounds<usize>>(
&mut self,
tree: &mut SegmentTree<T, L>,
range: R,
addend: T,
) {
let Range { start, end } = std::slice::range(range, ..tree.len());
self.assoc_(
tree,
(start, end - 1),
addend,
L::root(),
tree.root,
)
}
/// Lazy propagation
fn propagate(
&mut self,
tree: &mut SegmentTree<T, L>,
i: usize,
t: TreeCursor,
) {
if self[i] != zero!() {
let lfi = L::left(i, t);
let rhi = L::right(i, t);
tree[lfi] += &self[i];
self[lfi] = &self[lfi] + &self[i];
tree[rhi] += &self[i];
self[rhi] = &self[rhi] + &self[i];
self[i] = zero!();
}
}
fn assoc_(
&mut self,
tree: &mut SegmentTree<T, L>,
(l, r): (usize, usize),
addend: T,
i: usize,
t: TreeCursor,
) {
if l > r {
return;
}
if t.is_matched((l, r)) {
tree[i] += &addend;
self[i] += &addend;
} else {
self.propagate(tree, i, t);
self.assoc_(
tree,
(l, min(r, t.left().tr)),
addend.clone(),
L::left(i, t),
t.left(),
);
self.assoc_(
tree,
(max(l, t.right().tl), r),
addend,
L::right(i, t),
t.right(),
);
tree[i] = &tree[L::left(i, t)] + &tree[L::right(i, t)];
}
}
}
惰性更新只有当查询到某一层时，才会把更新推到分段树的下一层：
impl<T, L: TreeLayout> UpdaterAdd<T, L>
where
T: Clone + Sum + Add<Output = T> + Ord,
for<'a> T: AddAssign<&'a T>,
for<'a> &'a T: Add<&'a T, Output = T>,
{
pub fn query<R: RangeBounds<usize>>(
&mut self,
tree: &mut SegmentTree<T, L>,
range: R,
) -> T {
let Range { start, end } = std::slice::range(range, ..tree.len());
self.query_(
tree,
(start, end - 1),
L::root(),
tree.root,
)
}
fn query_(
&mut self,
tree: &mut SegmentTree<T, L>,
(l, r): (usize, usize),
i: usize,
t: TreeCursor,
) -> T {
if l > r {
return zero!();
}
if t.is_matched((l, r)) {
tree[i].clone()
} else {
self.propagate(tree, i, t);
let lf = self.query_(
tree,
(l, min(r, t.left().tr)),
L::left(i, t),
t.left(),
);
let rh = self.query_(
tree,
(max(l, t.right().tl), r),
L::right(i, t),
t.right(),
);
lf + rh
}
}
}
其他更新
对于给定区间的批量赋值，更加简单，只需要每个需要更新的区间存储一个标记位。当然如果是多个批量赋值，还是要一个完整的值的辅助数组。
推广到更高维度10
简单的二维分段树基本按照先构建第一个维度，然后在第一个维度下降到叶子时再构建第二个维度。
持久化版本
谈到持久化版本，就是树型结构，而且是指针构造的树型结构。
分段树自然很容易做成持久化版本，更新的时候直接复制更新路径就可以。
但是需要从本来的数组实现转为指针实现，这让这个问题变得有点儿鸡肋，因为性能损失实在有些不可接受。
动态分段
如果不能一次性地构建完整棵分段树，可以进行动态分段，只有当查询到某个区间的节点时再进行创建。
但是这也假设了指针实现版本的分段树，同样鸡肋。
注解
