高级数据结构：线段树|以及面向对象的编程语言代码实现

在编程实践中我们经常会遇到查询和更改区间的需求。为了支持这些操作，引入了一种称为线段树的数据结构。线段树具有以下性质：

1. 线段树是高度平衡的二叉树。可以是完全二叉树，也可以是完全二叉树，但这不是必要条件。
2. 线段树中的每个节点代表一个区间。父节点表示的区间是两个子节点的和。兄弟节点表示的区间不重叠。根节点代表整个区间

如图5.1所示，根节点代表区间[0,7]，左子节点代表区间[0,3]，右子节点代表区间[ 4, 7]。这是直接将父节点表示的区间一分为二的实现方法。虽然这种类型的线段树是最常见的，但是两个子节点之间的间隔长度实际上是可以随意改变的。这种改变的好处是树高度平衡，树的高度为log(n)，也就是说从根节点到任意叶子节点的路径长度为log(n)。

这样的数据结构有什么优点呢？我们来看这样一个问题。给定一个包含 N 个数字和 Q 个查询的数组 data[N]。每个查询的输入数据(a,b)是一对整数，要求打印data[a]和data[b]之间的最大值和最小值之差。比如N = 6，Q = 3，一个输入例子是

，输出分别是6,3,0。

如果直接做的话，每次查找都要找到其中的最大值和最小值这个区间，然后求差。这种做法显然效率很低。现在我们有了线段树，我们可以在树的节点中记录线段树中每个节点所代表的区间的最大值和最小值。不管这棵树是如何建造的。现在如果你有一个构造好的线段树并且你想检查特定区间的最大值和最小值，你只需要 O(log) 复杂度就可以得到结果。

以区间[0,4]为例，我们只需比较节点[0,3]和两个节点[4,4]的最大值和最小值即可得到[0, 4 ] ] 整个区间的最大值和最小值。而如果要查询的结果是整个区间的最大值和最小值，则可以直接返回根节点的最大值和最小值。见图 5.2。可见线段树大大提高了查询的效率。那么如何构建这样的线段树呢？

线段树本质上是一棵二叉树，所以构建线段树的方法和构建二叉树的方法是一样的，都是采用递归的方法来构建树。唯一的区别是节点的数据。每个节点存储它所代表的区间，以及这个区间的最大值和最小值。事实上，其本身所代表的区间也可以省略。然后我们会看到，通过巧妙地设置递归程序的参数，每个节点所代表的区间被省略了。

递归构造出一个节点的两个子节点后，当我们回溯到该节点时，我们可以通过比较两个子节点的最大值和最小值来更新该节点的最大值。最小值。如果这个节点是叶子节点，那么这个节点对应的区间只有一个数字，所以最大值和最小值都是这个数字。针对标题所示的例子构造一棵线段树，最终结果如图5.3所示。

struct node
{
	int max, min;
	node * pleft, * pright;
};

struct node line_tree[N * 2 + 10];
int data[N + 10];

int n;

int max, min;

int nodeCnt = 0;

node * getNewNode()
{
	return &line_tree[nodeCnt++];
}

node * buildTree(int left, int right)
{
	node * root = getNewNode();
	root->max = -1;
	root->min = MAX;

	if (left < right)
	{
		int mid = (left + right) >> 1;
		root->pleft = buildTree(left, mid);
		root->pright = buildTree(mid + 1, right);

		if (root->pleft->max > root->max)
			root->max = root->pleft->max;
		if (root->pright->max > root->max)
			root->max = root->pright->max;
		if (root->pleft->min < root->min)
			root->min = root->pleft->min;
		if (root->pright->min < root->min)
			root->min = root->pright->min;
	}
	else
	{
		root->min = data[left];
		root->max = data[left];
	}
	return root;
}

void question(node * root, int left, int right, int lleft, int lright)
{
	int mid;
	if (max > root->max && min < root->min)
		return;

	if (lleft == left && lright == right)
	{
		if (root->max > max)
			max = root->max;
		if (root->min < min)
			min = root->min;

		return;
	}

	mid = (left + right) >> 1;
	if (mid >= lleft)
	{
		if (mid >= lright)
			question(root->pleft, left, mid, lleft, lright);
		else
		{
			question(root->pleft, left, mid, lleft, mid);
			question(root->pright, mid + 1, right, mid + 1, lright);
		}
	}
	else
		question(root->pright, mid + 1, right, lleft, lright);
}

int main()
{
	int tmp, Q;
	int a, b;

	scanf_s("%d %d", &n, &Q);
	for (int i = 1; i <= n; i++)
		scanf_s("%d", data + i);

	node * root = buildTree(1, n);

	for (int i = 0; i < Q; i++)
	{
		scanf_s("%d %d", &a, &b);
		max = -1;
		min = MAX;
		question(root, 1, n, a, b);
		printf("%d\n", max - min);
	}

	return 0;
}

整个程序很容易理解。 buildTree函数与递归构建二叉树的程序没有什么不同。唯一的区别是，回溯到这个节点后，更新了这个节点的最大值和最小值。

这里重点关注提问功能的实现。 root表示当前查询的节点，left和right分别表示查询范围的左端和右端，left和right分别表示当前节点范围的左端和右端。如果left和left相等，right和right相等，则说明要查询的区间与当前节点表示的区间完全匹配。否则，取决于要查询的区间是落在当前节点的左孩子还是右孩子上。当

落在右孩子上时，查询区域完全位于当前节点区域的右半部分，即左边比中间大。在这种情况下，只需递归查询正确的子项即可。当落在左子区域时，则要搜索的区域完全位于当前节点区域的左半部分，即lright小于中心。在这种情况下，必须递归查询左孩子。如果希望查询区间跨越两个子区间，则将查询区间从中间分割，分别查询两个子节点。

分析程序可以看出，线段树虽然复杂，但它的根仍然是一棵二叉树。这就是为什么，在二叉树一节中，我们介绍了二叉树可以说是掌握数据结构的基石。如果你能深入理解二叉树的结构，掌握线段树将是一件非常容易的事情。