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

线段树【C语言】【C++】

article 2025/2/22 17:56:50

线段树（Segment Tree）是一种用于处理区间（segment）相关问题的数据结构，它可以高效地进行区间查询和区间更新。线段树特别适用于需要频繁查询某种统计信息（如最小值、最大值、总和等）并且可以快速进行修改（更新区间或单点）的场景。

1. 线段树的基本概念

结构：线段树通常被实现为一棵近似完全二叉树。每个节点表示某个区间的一个属性（如和、最大值等），叶子节点代表数组的元素。

构建：构建线段树的过程通常需要 O(n) 的时间复杂度，其中 n 是数组长度。

查询：对于给定的区间查询，线段树可以在 O(log n) 时间内返回结果。

更新：对某个元素的单点更新或对一个区间的更新也可以在 O(log n) 时间内完成。

2. 线段树的应用

线段树常用于解决以下问题：

查询区间的和、最大值、最小值、平均值等。
在给定区间内更新某些元素的值（如替换）。
单点更新（改变一个元素的值）。
支持询问区间中某个条件的统计。

3. 线段树的实现（注意，node数组大小一般为数据量的4倍！）

结构体和宏

C语言版本

#define max(a,b) ((a)>(b)?(a):(b))
typedef struct Node {
	int data, lazy;
} node;

C++版本

struct node {
	int data, lazy = 0;
};

build函数

构建线段树

构建线段树的基本步骤如下：

如果当前节点表示的区间是一个单点（即 left == right），将其值设置为数组中的对应值。
否则：
- 递归构建左子树和右子树。
- 根据子树的信息更新当前节点的值。

C语言版本

void build(int *data, node *tree, int rt, int left, int right) {
	if (left == right) {
		tree[rt].data = data[left];
		tree[rt].lazy = 0;
		return ;
	}
	int mid = (left + right) / 2;
	build(data, tree, 2 * rt, left, mid);
	build(data, tree, 2 * rt + 1, mid + 1, right);
	tree[rt].data = max(tree[2 * rt].data, tree[2 * rt + 1].data);
	tree[rt].lazy = 0;
}

C++版本

void build(const vector<int>&data, vector <node>&tree, int rt, int left, int right) {
	if (left == right) {
		tree[rt].data = data[left];
		return ;
	}
	int mid = left + (right - left) / 2;
	build(data, tree, 2 * rt, left, mid);
	build(data, tree, 2 * rt + 1, mid + 1, right);
	tree[rt].data = max(tree[2 * rt].data, tree[2 * rt + 1].data);
}

pushDown函数

懒惰更新是一种优化，通过在树的节点中额外存储一个懒惰变量（lazy），来延迟更新操作，从而提高效率。懒惰更新的基本思路是，当需要更新一个区间时，不立即更新子节点，而是标记当前节点，等到查询或者后续更新时再处理。

pushDown函数是对当前节点进行下发操作，将当前节点储存的懒惰变量下发给左右孩子，并归零懒惰变量。

C语言版本

void pushDown(node *tree, int rt) {
	if (tree[rt].lazy != 0) {
		tree[2 * rt].data += tree[rt].lazy;
		tree[2 * rt].lazy += tree[rt].lazy;
		tree[2 * rt + 1].data += tree[rt].lazy;
		tree[2 * rt + 1].lazy += tree[rt].lazy;
		tree[rt].lazy = 0;
	}
}

C++版本

void pushDown(vector<node>&tree, int rt) {
	if (tree[rt].lazy != 0) {
		tree[2 * rt].data += tree[rt].lazy;
		tree[2 * rt].lazy += tree[rt].lazy;
		tree[2 * rt + 1].data += tree[rt].lazy;
		tree[2 * rt + 1].lazy += tree[rt].lazy;
		tree[rt].lazy = 0;
	}
}

query函数

查询区间（代码展示的是查询最大值）

当我们想要查询某个区间 [ql, qr] 的值 (max, sum 等) 时，通常会执行以下操作：

如果查询的区间与当前节点的区间不重叠，返回一个很小的初始值（如 -inf）。
如果查询的区间完全包含当前区间，返回当前节点的值。
否则，递归查询左右子树的结果，并合并结果。

C语言版本

int query(node *tree, int rt, int left, int right, int ql, int qr) {
	if (ql > right || qr < left) {
		return -1e9;
	}
	if (ql <= left && qr >= right) {
		return tree[rt].data;
	}
	int mid = (left + right) / 2;
	pushDown(tree, rt);
	int lmax = query(tree, 2 * rt, left, mid, ql, qr);
	int rmax = query(tree, 2 * rt + 1, mid + 1, right, ql, qr);
	return max(lmax, rmax);
}

C++版本

int query(vector<node>&tree, int rt, int left, int right, int ql, int qr) {
	if (ql > right || qr < left) {
		return INT_MIN;
	}
	if (ql <= left && qr >= right) {
		return tree[rt].data;
	}
	int mid = left + (right - left) / 2;
	pushDown(tree, rt);
	int leftmax = query(tree, 2 * rt, left, mid, ql, qr);
	int rightmax = query(tree, 2 * rt + 1, mid + 1, right, ql, qr);
	return max(leftmax, rightmax);
}

update函数

更新操作

要更新某个元素（如将数组中索引为 idx 的元素更新为 value），可以：

如果当前节点表示的区间是 left == right，则直接更新该叶子节点。
否则，递归更新左右子树并更新当前节点的值。

C语言版本

void update(node *tree, int rt, int left, int right, int idx, int value) {
	if (left == right) {
		tree[rt].data = value;
		tree[rt].lazy = 0;
		return ;
	}
	int mid = (left + right) / 2;
	pushDown(tree, rt);
	if (idx <= mid) {
		update(tree, 2 * rt, left, mid, idx, value);
	} else {
		update(tree, 2 * rt + 1, mid + 1, right, idx, value);
	}
	tree[rt].data = max(tree[2 * rt].data, tree[2 * rt + 1].data);
}

C++版本

void update(vector<node>&tree, int rt, int left, int right, int idx, int value) {
	if (left == right) {
		tree[rt].data = value;
		tree[rt].lazy = 0;
		return ;
	}
	int mid = left + (right - left) / 2;
	pushDown(tree, rt);
	if (idx <= mid) {
		update(tree, 2 * rt, left, mid, idx, value);
	} else {
		update(tree, 2 * rt + 1, mid + 1, right, idx, value);
	}
	tree[rt].data = max(tree[2 * rt].data, tree[2 * rt + 1].data);
}

updateRange函数

区间更新：（代码展示的是查询最大值）

updateRange 函数用于在区间 [ul, ur] 上加上一个值 value，并使用 lazy 更新来延迟更新子节点。

C语言版本

void updateRange(node *tree, int rt, int left, int right, int ul, int ur, int value) {
	if (ul > right || ur < left)return ;
	if (ul <= left && ur >= right) {
		tree[rt].data += value;
		tree[rt].lazy += value;
		return ;
	}
	int mid = (left + right) / 2;
	pushDown(tree, rt);
	updateRange(tree, 2 * rt, left, mid, ul, ur, value);
	updateRange(tree, 2 * rt + 1, mid + 1, right, ul, ur, value);
	tree[rt].data = max(tree[2 * rt].data, tree[2 * rt + 1].data);
}

C++版本

void updateRange(vector<node>&tree, int rt, int left, int right, int ul, int ur, int value) {
	if (ul > right || ur < left) {
		return ;
	}
	if (ul <= left && ur >= right) {
		tree[rt].data += value;
		tree[rt].lazy += value;
		return ;
	}
	int mid = left + (right - left) / 2;
	pushDown(tree, rt);
	updateRange(tree, 2 * rt, left, mid, ul, ur, value);
	updateRange(tree, 2 * rt + 1, mid + 1, right, ul, ur, value);
	tree[rt].data = max(tree[2 * rt].data, tree[2 * rt + 1].data);
}