C++ 线段树原理与实现：数组版与节点版详解

线段树的原理

线段树（Segment Tree）是一种二叉搜索树，它将整个区间递归地划分为两半，直到每个节点代表一个单位区间或叶子节点。对于任意非叶子节点代表的区间 [a, b]，其中点为 mid = (a + b) / 2，左子节点覆盖 [a, mid]，右子节点覆盖 [mid + 1, b]。这种结构保证了线段树是一棵平衡二叉树，空间复杂度为 O(n)，其中 n 为区间长度。

相比前缀和数组在区间求和中 O(1) 查询但 O(n) 更新的局限性，线段树能够同时支持快速的区间查询和区间修改（如单点更新），两者的时间复杂度均为 O(logN)。这对于频繁修改数据的场景尤为关键。

以下展示了区间 [1, 7] 对应的线段树层级结构：

第 1 步：构建线段树

线段树的构建过程是递归地将数组区间二分。假设输入数组为 arr = {6, 4, 7, 5, 8, 3, 9}，我们需要建立一棵保存区间和的树。

在存储方式上，通常有两种策略：

• 数组存储（堆式编号）： 若根节点下标为 0，左子节点为 2 * node + 1，右子节点为 2 * node + 2。这种方式使用静态数组 tree[] 存储，空间利用率极高。对于长度为 7 的数组，由于线段树结点数接近 2 的幂次，通常会预留足够大的数组空间（如 1000）以避免边界计算错误。
• 节点存储： 使用链表结构，每个节点包含左右指针和值。这种方式更贴合面向对象思维，且无需预先估算数组大小。

以下是基于数组实现的构建代码。核心逻辑是：若当前区间 low == high，则为叶子节点，赋值并返回；否则计算中点，递归构建左右子树，最后将子节点的值相加赋给当前节点。

// 基于数组的线段树核心构建逻辑
private void buildTree(int node, int low, int high) {
    if(low == high) {
        tree[node] = arr[low];
        return;
    }
    int mid = low + (high - low) / 2;
    int lnode = 2 * node + 1;
    int rnode = 2 * node + 2;
    buildTree(lnode, low, mid);
    buildTree(rnode, mid + 1, high);
    // 父节点值为左右子节点之和
    tree[node] = tree[lnode] + tree[rnode];
}

第 2 步：单点更新

当数组中的某个元素值发生变化时（例如将 arr[4] 修改为 1），需要同步更新线段树中所有受影响的祖先节点。

更新操作的流程如下：

1. 从根节点开始递归查找目标索引所在的叶子节点。
2. 到达叶子节点（low == high && low == index）时，更新原始数组和树节点的值。
3. 在回溯过程中，重新计算当前节点的值为其左右子节点之和，确保路径上的所有节点保持正确性。

// 基于数组的单点更新逻辑
private void updateTree(int node, int low, int high, int index, int val) {
    if(low == high && low == index) {
        arr[index] = val;
        tree[node] = val;
        return;
    }
    int mid = low + (high - low) / 2;
    int lnode = 2 * node + 1;
    int rnode = 2 * node + 2;
    
    // 判断目标索引在左子树还是右子树
    if(index >= low && index <= mid) {
        updateTree(lnode, low, mid, index, val);
    } else {
        updateTree(rnode, mid + 1, high, index, val);
    }
    // 回溯更新父节点
    tree[node] = tree[lnode] + tree[rnode];
}

第 3 步：区间查询

查询区间 [L, R] 的和时，线段树通过将查询区间分解为若干个预设的树节点来加速计算，避免逐个累加。

查询逻辑遵循以下规则：

• 完全不相交： 若当前节点区间 [low, high] 与查询区间无交集（low > R || high < L），返回 0。
• 完全包含： 若当前节点区间完全落在查询区间内（low >= L && high <= R），直接返回该节点存储的值。
• 部分重叠： 否则，递归查询左右子树，并将结果相加。

// 基于数组的区间查询逻辑
private int queryTree(int node, int low, int high, int L, int R) {
    if(low > R || high < L) {
        return 0;
    } else if(low >= L && high <= R) {
        return tree[node];
    }
    int mid = low + (high - low) / 2;
    int lnode = 2 * node + 1;
    int rnode = 2 * node + 2;
    int sumLeft = queryTree(lnode, low, mid, L, R);
    int sumRight = queryTree(rnode, mid + 1, high, L, R);
    return sumLeft + sumRight;
}

两种实现版本的对比与测试

上述内容主要介绍了基于数组的实现。在实际工程中，除了数组版，还有基于节点的版本。节点版不使用固定大小的数组，而是通过创建 SegNode 对象来动态构建树。虽然空间开销略大，但其逻辑更加直观，且易于扩展支持更复杂的 Lazy Propagation（延迟标记）等操作。

无论是哪种实现，核心的递归思想是一致的：利用分治策略，将大问题拆解为小问题。测试代码验证了从初始构建、区间求和到单点修改后的数值变化，确保算法的正确性。

以上就是C++线段树原理与实现的详细内容，更多关于C++数据结构资料请关注本站其它相关文章！