线段树通过递归分治构建二叉树，实现区间求和、最值等操作的高效查询与更新。每个节点代表区间[l, r]并存储聚合信息，叶子节点对应原数组元素，非叶子节点合并子节点结果。常用数组模拟存储，根节点索引为1，左右子节点分别为2i和2i+1，空间一般开4*n。建树、单点更新、区间查询时间复杂度均为O(log n)。支持区间更新时需引入懒标记（lazy propagation）延迟下传修改，提升效率。可扩展维护最大值、最小值、异或和等，核心在于修改合并逻辑。掌握递归建树、区间覆盖判断与分治查询是关键。
线段树是一种高效处理区间查询和区间更新的数据结构，常用于算法竞赛中解决如区间求和、区间最值、区间更新等问题。它通过将区间递归划分成多个子区间，构建一棵二叉树，实现 O(log n) 的查询与更新效率。
线段树的基本结构与原理
线段树是一棵二叉树，每个节点代表一个区间 [l, r]，存储该区间内某个聚合信息（如和、最大值等）。叶子节点对应原数组的单个元素，非叶子节点是其左右子节点的信息合并结果。
对于长度为 n 的数组，线段树通常用数组模拟，根节点在索引 1，左子节点为 2*i，右子节点为 2*i+1。总空间建议开 4*n 防止越界。
实现区间求和线段树
以下是一个支持区间求和与单点修改的线段树实现：
立即学习“C++免费学习笔记（深入）”；
#include #include using namespace std;class SegmentTree {private:vector tree; // 存储线段树节点值int n; // 原数组长度
void build(const vector& 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 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& 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);}
};
使用示例与常见扩展
使用上面的类非常简单：
int main() { vector arr = {1, 3, 5, 7, 9, 11}; SegmentTree st(arr);cout << st.query(1, 3) << endl; // 输出 3+5+7 = 15st.update(2, 10); // 把索引2的值改为10cout << st.query(1, 3) << endl; // 输出 3+10+7 = 20return 0;
}
若要支持区间更新（如区间加法），需引入懒标记（lazy propagation），在节点上维护一个延迟更新值，避免每次都下传更新。
线段树还可扩展为维护最大值、最小值、异或和等，只需修改合并逻辑（tree[node] = max(left, right) 等）。
基本上就这些。掌握建树、查询、更新三个核心操作，就能应对大多数区间问题。线段树写起来有一定模板性，多练几次就能熟练。关键是理解递归分治的思想和区间覆盖的判断逻辑。
以上就是C++怎么实现一个线段树数据结构_C++算法竞赛与区间查询问题的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485243.html
微信扫一扫 
支付宝扫一扫 
