线段树

线段树是一种基于分治思想的二叉树结构，用于高效处理区间或线段的查询与更新操作。

提示

线段树擅长处理动态的顺序统计问题，特别是在动态变化的空间中快速找到第 k 个空位。

线段树的本质是将区间划分为左右两个区间，递归求解。整个线段被划分为树结构，如下图：

该线段树基于数组 [1, 2, 3, 4, 5, 6, 7, 8] 构建，每个节点存储对应区间的和。建树过程通常采用递归自顶向下的方式，其节点编号与区间划分遵循以下规律：

• 对于节点 $d_i$，其左儿子节点为 $d_{2\times i}$，右儿子节点为 $d_{2\times i+1}$。
• 若 $d_i$ 表示区间 $[s,t]$（即 $d_i = a_s + a_{s+1} + \cdots + a_t$），则左儿子表示区间 $\left[s, \frac{s+t}{2}\right]$，右儿子表示区间 $\left[\frac{s+t}{2}+1, t\right]$。

在实现时，采用递归建树：
设当前根节点为 $p$，若其管辖的区间长度已经是 $1$(当前节点对应的区间只有一个元素)，则直接根据 $a$ 数组上相应位置的值初始化该节点(叶子节点存储原数组中该位置的值)；否则将区间从中点分割为两个子区间，分别进入左右子节点递归建树，最后合并两个子节点的信息。

具体建树过程如下：

1. 根节点：区间 $[1,8]$，其值等于左子区间 $[1,4]$ 与右子区间 $[5,8]$ 的和。
2. 递归左子树：
   • 节点 $[1,4]$ 的值等于 $[1,2]$ 与 $[3,4]$ 的和。
   • 节点 $[1,2]$ 的值等于 $[1,1]$ 与 $[2,2]$ 的和，叶子节点 $[1,1]$ 存储 $1$，$[2,2]$ 存储 $2$，得 $[1,2]=3$。
   • 节点 $[3,4]$ 的值等于 $[3,3]$ 与 $[4,4]$ 的和，叶子 $[3,3]$ 存储 $3$，$[4,4]$ 存储 $4$，得 $[3,4]=7$。
   • 因此 $[1,4]=3+7=10$。
3. 递归右子树：
   • 节点 $[5,8]$ 的值等于 $[5,6]$ 与 $[7,8]$ 的和。
   • 节点 $[5,6]$ 的值等于 $[5,5]$ 与 $[6,6]$ 的和，叶子 $[5,5]$ 存储 $5$，$[6,6]$ 存储 $6$，得 $[5,6]=11$。
   • 节点 $[7,8]$ 的值等于 $[7,7]$ 与 $[8,8]$ 的和，叶子 $[7,7]$ 存储 $7$，$[8,8]$ 存储 $8$，得 $[7,8]=15$。
   • 因此 $[5,8]=11+15=26$。
4. 根节点值：$[1,8]=10+26=36$。

线段树的高度是$\lceil \log_2 n \rceil + 1$（若根节点高度为1），其中$n$是原数组的长度。

线段树是一棵平衡二叉树，其叶子节点对应原数组的每个元素。为了便于数组存储，通常将其构建为一棵完全二叉树（或近似完全二叉树）。对于长度为 $n$ 的数组，叶子节点个数为 $n$，但为了满足完全二叉树的结构，实际叶子节点数会向上取整到 $2^{\lceil \log_2 n \rceil}$。

• 若根节点高度为 $1$，则树的高度 $h = \lceil \log_2 n \rceil + 1$。
• 若根节点高度为 $0$，则 $h = \lceil \log_2 n \rceil$。

看两个例子：

• $n = 8$：$\lceil \log_2 8 \rceil = 3$，高度 $= 4$（根高度 $1$）或 $3$（根高度 $0$）。
• $n = 5$：$\lceil \log_2 5 \rceil = 3$，高度同样为 $4$（根高度 $1$），因为需要补齐到 $8$ 个叶子。

在线段树的数组实现中，通常开辟 $4n$ 大小的空间，正是基于这个高度（$2^{h} \approx 4n$）来保证不越界。

因此，线段树的高度是 $O(\log n)$ 级别的。

建树代码：

void build(int p, int l, int r) {
    // p: 当前节点在数组中的下标。
    // l: 当前节点所管辖区间的左端点（包含），对应原数组 `a` 的下标。
    // r: 当前节点所管辖区间的右端点（包含），对应原数组 `a` 的下标。
    if (l == r) {// 递归基：区间只有一个元素
        tree[p] = a[l];// 叶子节点直接存储原数组该位置的值
        return;// 结束当前分支的递归
    }
    int mid = (l + r) / 2;// 计算当前区间的中点，将区间分成 [l, mid] 和 [mid+1, r] 两半
    build(p * 2, l, mid);// 递归构建左子节点，左子节点下标为 p*2，区间为 [l, mid]
    build(p * 2 + 1, mid + 1, r);// 递归构建右子节点，右子节点下标为 p*2+1，区间为 [mid+1, r]
    tree[p] = tree[p * 2] + tree[p * 2 + 1];// 回溯时合并左右子树的信息，这里以“和”为例
}