C++怎么实现一个线段树_C++数据结构与线段树实现-C++-PHP中文网

C++怎么实现一个线段树_C++数据结构与线段树实现

下次还敢

发布： 2025-11-21 16:33:13

原创

644人浏览过

线段树通过数组模拟完全二叉树实现区间和查询与单点更新，支持高效处理区间聚合操作。

c++怎么实现一个线段树_c++数据结构与线段树实现

线段树是一种用于高效处理区间查询和更新操作的数据结构，常见于解决区间最值、区间和、区间更新等问题。在C++中，通过数组模拟完全二叉树的方式实现线段树，既高效又简洁。

线段树的基本思想

线段树将一个数组的区间递归地划分为左右两部分，每个节点代表一个区间，存储该区间的聚合信息（如和、最大值等）。树的根节点表示整个数组区间 [0, n-1]，叶子节点对应单个元素。

主要支持两种操作：

构建（Build）：根据原始数组建立线段树
查询（Query）：查询某个区间内的聚合值
更新（Update）：单点或区间更新，并维护树结构

基于数组的线段树实现

使用一维数组 tree 存储线段树节点，通常大小为原始数组长度的4倍，以保证足够空间。

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

以下是一个实现区间和查询与单点更新的线段树示例：

GPTKit

一个AI文本生成检测工具

108

查看详情

#include <iostream>
#include <vector>
using namespace std;
<p>class SegmentTree {
private:
vector<int> tree;
int n;</p><pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">void build(const vector<int>& arr, int node, int start, int end) {
    if (start == end) {
        tree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        build(arr, node * 2, start, mid);
        build(arr, node * 2 + 1, mid + 1, end);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

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]; // 完全包含
    int mid = (start + end) / 2;
    return query(node * 2, start, mid, l, r) +
           query(node * 2 + 1, mid + 1, end, l, r);
}

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

登录后复制

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

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

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

登录后复制

};

使用方式示例：

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

return 0;

登录后复制

}