c++怎么实现一个线段树_C++中实现区间查询与更新的线段树算法-C++-PHP中文网

c++怎么实现一个线段树_C++中实现区间查询与更新的线段树算法

尼克

发布： 2025-11-19 06:55:09

原创

881人浏览过

线段树是一种高效处理区间查询与更新的数据结构，通过数组模拟二叉树实现，支持区间和、最值等操作。其核心包括构建（build）、查询（query）和更新（update）三个函数，并利用懒惰标记（lazy propagation）优化区间修改，避免重复计算。树的每个节点代表原数组的一个区间，根节点覆盖整个区间，叶子节点对应单个元素。通常将线段树数组大小设为原数组长度的4倍以保证空间充足。构建过程递归分割区间并合并子节点值；查询时若当前节点完全包含于目标区间则直接返回值，否则下放懒惰标记后递归查询左右子树；更新时先下放标记，若当前区间完全被覆盖则打上懒惰标记并立即应用，否则继续递归更新子区间并回传结果。该结构适用于频繁进行区间操作的场景，具有较高的时间效率和实用性。

c++怎么实现一个线段树_c++中实现区间查询与更新的线段树算法

线段树是一种高效处理区间查询和区间更新的数据结构，特别适用于频繁进行区间操作的场景，比如求区间和、区间最小值/最大值，以及支持单点或区间修改。在C++中实现一个支持区间查询与懒惰更新（lazy propagation）的线段树并不复杂，下面是一个完整且实用的实现。

线段树基本结构设计

线段树本质上是一棵二叉树，通常用数组模拟。每个节点代表原数组的一个区间，根节点代表整个区间 [0, n-1]，叶子节点代表单个元素。

为了方便实现，我们使用以下成员：

tree[]：存储线段树节点的值（如区间和）
lazy[]：懒惰标记数组，用于延迟更新
n：原始数组长度

线段树数组大小一般开到 4 倍原数组长度，以保证空间充足。

立即学习“C++免费学习笔记（深入）”；

构建线段树（build）

从底向上构造线段树，递归地将区间一分为二，直到单个元素为止。

语鲸

AI智能阅读辅助工具

252

查看详情

void build(vector<int>& arr, int node, int start, int end) {
    if (start == end) {
        tree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        build(arr, 2*node, start, mid);
        build(arr, 2*node+1, mid+1, end);
        tree[node] = tree[2*node] + tree[2*node+1]; // 区间和
    }
}

登录后复制

区间查询（query）

查询 [l, r] 范围内的和，过程中需要处理懒惰标记。

int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0; // 无交集
    if (l <= start && end <= r) return tree[node]; // 完全包含
<pre class='brush:php;toolbar:false;'>int mid = (start + end) / 2;
push(node, start, end); // 下放懒惰标记
int left_sum = query(2*node, start, mid, l, r);
int right_sum = query(2*node+1, mid+1, end, l, r);
return left_sum + right_sum;

登录后复制

}

区间更新（update）与懒惰传播（push）

对区间 [l, r] 增加一个值 val，使用懒惰标记避免重复计算。

void push(int node, int start, int end) {
    if (lazy[node]) {
        tree[node] += (end - start + 1) * lazy[node];
        if (start != end) { // 非叶子，传递标记
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
<p>void update(int node, int start, int end, int l, int r, int val) {
push(node, start, end); // 先下放标记
if (r < start || end < l) return;
if (l <= start && end <= r) {
lazy[node] += val;
push(node, start, end); // 立即应用
return;
}</p><pre class='brush:php;toolbar:false;'>int mid = (start + end) / 2;
update(2*node, start, mid, l, r, val);
update(2*node+1, mid+1, end, l, r, val);
tree[node] = tree[2*node] + tree[2*node+1];

登录后复制

}

基本上就这些。初始化时调用 build，查询调用 query，更新调用 update，注意每次操作都处理 lazy 标记。这种实现方式简洁高效，适合大多数区间问题。

以上就是c++++怎么实现一个线段树_C++中实现区间查询与更新的线段树算法的详细内容，更多请关注php中文网其它相关文章！