算法详解：线段树的C++实现

算法详解：线段树的C++实现

引用

CSDN

1.

https://m.blog.csdn.net/2401_86771711/article/details/141870725

线段树（Segment Tree）是一种用于处理区间查询和区间更新的高效数据结构。它可以将一个数组分成多个小区间，并在每个小区间上存储一些信息（如区间的最小值、最大值、和等），以便快速查询或更新整个数组中的某个区间。

线段树的基本结构

线段树是一个二叉树，其中每个节点代表数组的一个区间。每个节点存储的信息通常是该区间内所有元素的一个汇总（例如，和、最小值、最大值等）。对于节点node[i]，其左子节点为node[2*i+1]，右子节点为node[2*i+2]（假设数组索引从0开始）。

1. 定义节点结构体

首先，我们需要定义线段树的节点结构体，通常包含区间的起始和结束位置，以及该区间的汇总信息。

#include <vector> 
#include <iostream> 
using namespace std; 
struct SegmentTreeNode { 
int start, end; 
long long sum; // 假设存储的是和 
SegmentTreeNode *left, *right; 
SegmentTreeNode(int s, int e) : start(s), end(e), sum(0), left(nullptr), right(nullptr) {} 
};  

2. 构建线段树

接下来，我们需要一个函数来构建线段树。

SegmentTreeNode* buildTree(const vector<int>& nums, int start, int end) { 
if (start > end) return nullptr; 
SegmentTreeNode* node = new SegmentTreeNode(start, end); 
if (start == end) { 
node->sum = nums[start]; 
return node; 
} 
int mid = (start + end) / 2; 
node->left = buildTree(nums, start, mid); 
node->right = buildTree(nums, mid + 1, end); 
node->sum = node->left->sum + node->right->sum; 
return node; 
}  

3. 单点更新

更新线段树中某个位置的值，并向上更新所有祖先节点的信息。

void update(SegmentTreeNode* node, int index, int value) { 
if (node->start == node->end) { 
node->sum = value; 
return; 
} 
int mid = (node->start + node->end) / 2; 
if (index <= mid) { 
update(node->left, index, value); 
} else { 
update(node->right, index, value); 
} 
node->sum = node->left->sum + node->right->sum; 
}  

4. 区间查询

查询线段树中某个区间的和。

long long query(SegmentTreeNode* node, int start, int end) { 
if (start > node->end || end < node->start) return 0; 
if (start <= node->start && node->end <= end) { 
return node->sum; 
} 
int mid = (node->start + node->end) / 2; 
long long leftSum = query(node->left, start, end); 
long long rightSum = query(node->right, start, end); 
return leftSum + rightSum; 
}  

5. 主函数和测试

int main() { 
vector<int> nums = {1, 3, 5, 7, 9, 11}; 
SegmentTreeNode* root = buildTree(nums, 0, nums.size() - 1); 
cout << "Initial sum of range [1, 3]: " << query(root, 1, 3) << endl; // 应输出 15 
update(root, 2, 4); // 将索引为2的元素从5更新为4 
cout << "Sum of range [1, 3] after update: " << query(root, 1, 3) << endl; // 应输出 14 
return 0; 
}  

主要应用场景：

1. 区间查询

• 区间和查询：最常见的应用场景之一，用于查询数组中某个区间的元素和。
• 区间最小值/最大值查询：可以查询数组中某个区间的最小值或最大值。
• 区间最值统计：除了最小值和最大值，还可以统计区间内的其他最值（如第二小值、次大值等）。
• 区间内特定元素数量查询：查询区间内满足特定条件的元素数量。

2. 区间更新

• 单点更新：更新数组中某个元素的值，并更新线段树中相关节点的信息。
• 区间更新：将数组中某个区间的所有元素都更新为同一个值，或者对每个元素应用某种操作（如加法、乘法等）。

3. 复杂区间查询和更新

• 区间合并：某些问题需要将多个区间进行合并，如区间覆盖或区间合并等问题。
• 区间内元素操作：如区间的最小公倍数（LCM）或最大公约数（GCD）查询、区间排序等。

4. 实际应用

• 数据压缩：在处理大规模数据时，线段树可以帮助减少数据存储和传输的开销。
• 资源分配：在操作系统或网络管理中，线段树可用于高效地分配和回收资源（如内存、带宽等）。
• 图形学：在图形处理中，线段树可用于加速区间查询和更新操作，如屏幕空间环境光遮蔽（SSAO）等。
• 金融领域：在金融数据分析中，线段树可用于快速计算股票等金融产品的历史数据指标（如移动平均线、成交量等）。

5. 高效性

线段树基于平衡二叉树的结构，每一次修改、查询的时间复杂度都为O(logn)，这使得它在处理大规模数据集时具有非常高的效率。相比一般的线性结构（如数组或链表），线段树在区间查询和更新操作上具有显著的优势。

综上所述，线段树在处理与区间相关的查询和更新问题时具有广泛的应用场景，并且由于其高效性而备受青睐。在实际应用中，可以根据具体问题的需求选择合适的线段树变种或优化策略来提高算法的性能。

以上是一个简单的线段树实现，用于支持区间和查询和单点更新。通过适当修改节点存储的信息和更新、查询的逻辑，线段树可以支持更复杂的区间查询和更新操作。