当前位置：首页 > news >正文

线段树：数据结构中的超级英雄

news 2025/5/10 7:10:56

在数据结构的世界里，线段树就像是一位超级英雄，能够高效地解决区间查询和更新问题。作为 C++ 算法小白，今天我就带大家一起认识这位超级英雄，揭开线段树的神秘面纱。

什么是线段树？

线段树是一种二叉树数据结构，它主要用于高效处理区间查询（如求和、求最大值、求最小值等）和区间更新（如将区间内的所有元素加上一个值）。线段树的每个节点表示一个区间，根节点表示整个区间，叶子节点表示单个元素。

线段树的特点

二叉树结构：每个节点要么是叶子节点，要么有两个子节点。
区间划分：每个节点表示一个区间，左子节点表示左半区间，右子节点表示右半区间。
高效处理区间操作：线段树能够在 O (log n) 的时间复杂度内完成区间查询和区间更新操作。

线段树的基本操作

构建线段树

我们以区间求和为例，来看看如何构建线段树。

cpp

#include <iostream>
#include <vector>using namespace std;// 线段树节点结构
struct SegmentTreeNode {int start, end, sum;SegmentTreeNode* left;SegmentTreeNode* right;SegmentTreeNode(int s, int e) : start(s), end(e), sum(0), left(nullptr), right(nullptr) {}
};// 构建线段树
SegmentTreeNode* buildTree(vector<int>& nums, int start, int end) {if (start > end) return nullptr;SegmentTreeNode* root = new SegmentTreeNode(start, end);if (start == end) {root->sum = nums[start];return root;}int mid = start + (end - start) / 2;root->left = buildTree(nums, start, mid);root->right = buildTree(nums, mid + 1, end);root->sum = root->left->sum + root->right->sum;return root;
}

代码解释

SegmentTreeNode 结构体：定义了线段树的节点结构，包含区间的起始位置 start、结束位置 end、区间和 sum，以及左右子节点指针。
buildTree 函数：递归构建线段树。如果当前区间只有一个元素，则直接将该元素的值赋给节点的 sum。否则，将区间分成两半，分别递归构建左右子树，然后将左右子树的和相加赋给当前节点的 sum。

区间查询

查询区间 [i, j] 的和。

cpp

// 区间查询
int query(SegmentTreeNode* root, int i, int j) {if (!root || i > root->end || j < root->start) return 0;if (i <= root->start && j >= root->end) return root->sum;int mid = root->start + (root->end - root->start) / 2;if (j <= mid) return query(root->left, i, j);if (i > mid) return query(root->right, i, j);return query(root->left, i, j) + query(root->right, i, j);
}

代码解释

query 函数：递归查询区间 [i, j] 的和。如果当前节点的区间完全包含在查询区间内，则直接返回该节点的 sum。否则，根据查询区间与当前节点区间的关系，递归查询左子树或右子树，或者同时查询左右子树并将结果相加。

单点更新

将位置 idx 的值更新为 val。

cpp

// 单点更新
void update(SegmentTreeNode* root, int idx, int val) {if (!root || idx < root->start || idx > root->end) return;if (root->start == root->end) {root->sum = val;return;}int mid = root->start + (root->end - root->start) / 2;if (idx <= mid) update(root->left, idx, val);else update(root->right, idx, val);root->sum = root->left->sum + root->right->sum;
}

代码解释

update 函数：递归更新位置 idx 的值。如果当前节点是叶子节点，则直接更新该节点的 sum。否则，根据 idx 与当前节点区间的关系，递归更新左子树或右子树，然后更新当前节点的 sum。

例题讲解

问题描述

给定一个数组 nums，以及一些查询和更新操作，要求高效地处理这些操作。查询操作是求区间 [i, j] 的和，更新操作是将位置 idx 的值更新为 val。

代码示例

cpp

#include <iostream>
#include <vector>using namespace std;// 线段树节点结构
struct SegmentTreeNode {int start, end, sum;SegmentTreeNode* left;SegmentTreeNode* right;SegmentTreeNode(int s, int e) : start(s), end(e), sum(0), left(nullptr), right(nullptr) {}
};// 构建线段树
SegmentTreeNode* buildTree(vector<int>& nums, int start, int end) {if (start > end) return nullptr;SegmentTreeNode* root = new SegmentTreeNode(start, end);if (start == end) {root->sum = nums[start];return root;}int mid = start + (end - start) / 2;root->left = buildTree(nums, start, mid);root->right = buildTree(nums, mid + 1, end);root->sum = root->left->sum + root->right->sum;return root;
}// 区间查询
int query(SegmentTreeNode* root, int i, int j) {if (!root || i > root->end || j < root->start) return 0;if (i <= root->start && j >= root->end) return root->sum;int mid = root->start + (root->end - root->start) / 2;if (j <= mid) return query(root->left, i, j);if (i > mid) return query(root->right, i, j);return query(root->left, i, j) + query(root->right, i, j);
}// 单点更新
void update(SegmentTreeNode* root, int idx, int val) {if (!root || idx < root->start || idx > root->end) return;if (root->start == root->end) {root->sum = val;return;}int mid = root->start + (root->end - root->start) / 2;if (idx <= mid) update(root->left, idx, val);else update(root->right, idx, val);root->sum = root->left->sum + root->right->sum;
}int main() {vector<int> nums = {1, 3, 5, 7, 9};SegmentTreeNode* root = buildTree(nums, 0, nums.size() - 1);// 查询区间 [1, 3] 的和cout << "Sum of interval [1, 3]: " << query(root, 1, 3) << endl;// 更新位置 2 的值为 6update(root, 2, 6);// 再次查询区间 [1, 3] 的和cout << "Sum of interval [1, 3] after update: " << query(root, 1, 3) << endl;return 0;
}