数据结构——段树 数据结构树的节点

数据结构教程：段树（Segment Tree）

段树是一种基于完全二叉树的数据结构，专为解决数组区间查询和修改问题而设计。它能将一个数组的所有连续子区间的信息高效地存储在树中，使得对任意区间的查询或更新操作可以在O(log n)的时间复杂度内完成。

基本概念与结构

? 段树的每个节点关联着原数组的一个连续子区间。

? 根节点代表整个数组，其左右子节点分别表示左半部分和右半部分。

? 通过递归划分数组区间直到长度为1，形成叶子节点，对应原数组单个元素。

基本操作

1. 构建段树：

? 输入给定数组arr和大小n，创建大小为4*n的数组模拟完全二叉树，并自底向上计算每个节点对应的区间和或其他信息。

2. 查询操作：

? 给定一个查询区间[l, r]，从根节点开始自顶向下查找，合并沿途节点信息以获取该区间的结果。

3. 更新操作：

? 当需要修改原数组某个位置值时，找到对应影响范围的段树节点进行更新，并回溯到根节点同步所有相关节点信息。

C++ 示例代码片段（区间求和为例）

class SegmentTree {
private:
	vector<int> tree; // 存储段树的数组
public:
	// 构造函数，输入为原数组arr和大小n
	SegmentTree(vector<int>& arr, int n) {
		tree.resize(4 * n);
		build(arr, 0, 0, n - 1);
	}
	// 从下至上构建段树
	void build(vector<int>& arr, int node, int start, int end) {
		if (start == end) {
			tree[node] = arr[start];
			return;
		}
		int mid = start + (end - start) / 2;
		build(arr, 2 * node + 1, start, mid); // 左子树
		build(arr, 2 * node + 2, mid + 1, end); // 右子树
		tree[node] = tree[2 * node + 1] + tree[2 * node + 2]; // 合并区间和
	}
	// 查询区间[l, r]的和
	int query(int l, int r) {
		return query(0, 0, n - 1, l, r);
	}
	// 自顶向下查询区间[l, r]的和
	int query(int node, int start, int end, int l, int r) {
		// 空区间或不在查询范围内返回0
		if (l > end || r < start)
			return 0;
		// 区间完全包含在查询范围内，直接返回节点值
		if (l <= start && end <= r)
			return tree[node];
		int mid = start + (end - start) / 2;
		// 分别查询左右子区间和，然后相加
		return query(2 * node + 1, start, mid, l, r) + query(2 * node + 2, mid + 1, end, l, r);
	}
	// 更新第pos位置的值为val（这里仅展示框架）
	void update(int pos, int val) {
		update(0, 0, n - 1, pos, val);
	}
	// 自顶向下更新第pos位置的值为val
	void update(int node, int start, int end, int pos, int val) {
		// 更新到叶节点后，根据实际情况调整父节点信息
	}
};

总结来说，段树通过构建一棵反映数组区间变化的完全二叉树，极大地提高了涉及动态区间查询、修改等问题的处理效率。尽管本例只展示了区间求和的操作，但实际应用中，段树还可以用于求区间最大/最小值、区间加法、区间翻转等多种问题。