C++怎么实现一个线段树数据结构_C++算法竞赛与区间查询问题-C++-PHP中文网

C++怎么实现一个线段树数据结构_C++算法竞赛与区间查询问题

冰火之心

发布： 2025-11-21 15:27:01

原创

546人浏览过

线段树通过递归分治构建二叉树，实现区间求和、最值等操作的高效查询与更新。每个节点代表区间[l, r]并存储聚合信息，叶子节点对应原数组元素，非叶子节点合并子节点结果。常用数组模拟存储，根节点索引为1，左右子节点分别为2i和2i+1，空间一般开4*n。建树、单点更新、区间查询时间复杂度均为O(log n)。支持区间更新时需引入懒标记（lazy propagation）延迟下传修改，提升效率。可扩展维护最大值、最小值、异或和等，核心在于修改合并逻辑。掌握递归建树、区间覆盖判断与分治查询是关键。

c++怎么实现一个线段树数据结构_c++算法竞赛与区间查询问题

线段树是一种高效处理区间查询和区间更新的数据结构，常用于算法竞赛中解决如区间求和、区间最值、区间更新等问题。它通过将区间递归划分成多个子区间，构建一棵二叉树，实现 O(log n) 的查询与更新效率。

线段树的基本结构与原理

线段树是一棵二叉树，每个节点代表一个区间 [l, r]，存储该区间内某个聚合信息（如和、最大值等）。叶子节点对应原数组的单个元素，非叶子节点是其左右子节点的信息合并结果。

对于长度为 n 的数组，线段树通常用数组模拟，根节点在索引 1，左子节点为 2*i，右子节点为 2*i+1。总空间建议开 4*n 防止越界。

实现区间求和线段树

以下是一个支持区间求和与单点修改的线段树实现：

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

#include <iostream>
#include <vector>
using namespace std;
<p>class SegmentTree {
private:
vector<int> tree;  // 存储线段树节点值
int n;              // 原数组长度</p><pre class='brush:php;toolbar:false;'>void build(const vector<int>& arr, int node, int l, int r) {
    if (l == r) {
        tree[node] = arr[l];
        return;
    }
    int mid = (l + r) / 2;
    build(arr, node * 2, l, mid);
    build(arr, node * 2 + 1, mid + 1, r);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void update(int node, int l, int r, int idx, int val) {
    if (l == r) {
        tree[node] = val;
        return;
    }
    int mid = (l + r) / 2;
    if (idx <= mid)
        update(node * 2, l, mid, idx, val);
    else
        update(node * 2 + 1, mid + 1, r, idx, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int query(int node, int l, int r, int ql, int qr) {
    if (qr < l || ql > r) return 0;
    if (ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return query(node * 2, l, mid, ql, qr) +
           query(node * 2 + 1, mid + 1, r, ql, qr);
}

登录后复制

public: SegmentTree(const vector<int>& arr) { n = arr.size(); tree.resize(4 * n); build(arr, 1, 0, n - 1); }

void update(int idx, int val) {
    update(1, 0, n - 1, idx, val);
}

int query(int l, int r) {
    return query(1, 0, n - 1, l, r);
}

登录后复制

};

Alkaid.art

专门为Phtoshop打造的AIGC绘画插件

153

查看详情

使用示例与常见扩展

使用上面的类非常简单：

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    SegmentTree st(arr);
<pre class='brush:php;toolbar:false;'>cout << st.query(1, 3) << endl;  // 输出 3+5+7 = 15
st.update(2, 10);                 // 把索引2的值改为10
cout << st.query(1, 3) << endl;  // 输出 3+10+7 = 20

return 0;

登录后复制

}

若要支持区间更新（如区间加法），需引入懒标记（lazy propagation），在节点上维护一个延迟更新值，避免每次都下传更新。

线段树还可扩展为维护最大值、最小值、异或和等，只需修改合并逻辑（tree[node] = max(left, right) 等）。

基本上就这些。掌握建树、查询、更新三个核心操作，就能应对大多数区间问题。线段树写起来有一定模板性，多练几次就能熟练。关键是理解递归分治的思想和区间覆盖的判断逻辑。

以上就是C++怎么实现一个线段树数据结构_C++算法竞赛与区间查询问题的详细内容，更多请关注php中文网其它相关文章！