线段树

定义

如其名，线段 $\Leftrightarrow$ 区间。

将线段不断二分作为子节点，从而构成树缓存。

用途

维护区间信息，支持：

单点修改
区间修改
区间查询

实现

Info

由于时间复杂度问题，涉及多种运算及更多更复杂的情况，无法总结出一个 generic 的线段树，故这里只给出一个支持区间加法 & 区间求和的线段树实现。

区间 Utils

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


template<typename T>
struct SegmentTree {
	static constexpr auto left(size_t p) -> size_t { return p << 1; }
	static constexpr auto right(size_t p) -> size_t { return (p << 1) | 1; }
	static constexpr auto mid(size_t s, size_t t) -> size_t { 
		return (s + t) >> 1; 
	}
	static constexpr auto len(size_t s, size_t t) -> size_t {
		return t - s + 1;
	}
	
	// ...
};

结构

对于给定的数据数组 $a[n]$，维护一个池化缓存数组 $d[4n]$ 管理所有结点内存。

缓存数组大小分析

TODO

其中 $d[i]$ 的子节点为 $d[2i]$ 和 $d[2i + 1]$，他们的管辖区间是：

父节点 $d[i]$ $\Rightarrow$ $[s .. t]$
左儿子 $d[2i]$ $\Rightarrow$ $[s .. \frac{s + t}{2}]$
右儿子 $d[2i + 1]$ $\Rightarrow$ $[\frac{s + t}{2} + 1 .. t]$

1
2
3
4
5


template<typename T>
struct SegmentTree {
	std::vector<T> tree;
	std::vector<T> lazy; // lazy add
};

于是建树如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


/**
 * @brief 建树
 * @param s 左边界
 * @param t 右边界
 * @param p 当前节点(父节点)
 */
template<typename T>
auto SegmentTree<T>::build(size_t s, size_t t, size_t p) -> void {
	if (s == t) {
		d[p] = a[s];
		return;
	}
	size_t m = s + ((s + t) >> 1); // middle
	build(s, m, p * 2);
	build(m + 1, t, p * 2 + 1);
	d[p] = op(d[p * 2], d[p * 2 + 1]);
}

Lazy Tag

为了控制时间复杂度，我们没必要每次修改都维护更新整棵树。我们只修改实际数据，打上标记，在下次询问时才更新树。这个标记就叫 「lazy tag」，这种优化方法叫做 「lazy propagation」。

注意，每个节点的 lazy tag 是针对子区间的未更新标记，当前节点的修改是即时更新的。

为了维护 lazy tag，我们引入 pushdown 操作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


template<typename T>
auto SegmentTree<T>::pushdown(size_t s, size_t t, size_t p) -> void {
	if (lazy[p] != 0) {
		auto m = mid(s, t);
		lazy[left(p)] += lazy[p];
		lazy[right(p)] += lazy[p];
		tree[left(p)] += lazy[p] * len(s, m);
		tree[right(p)] += lazy[p] * len(m + 1, t);
		lazy[p] = 0;
	}
}

Attention

pushdown 保证了子区间的正确性，所以在操作子区间前都要 pushdown。

为了方便记忆，还可以引入一个 pushup 函数，用于在子区间更新后更新父区间：

1
2
3
4


template<typename T>
auto SegmentTree<T>::pushup(size_t s, size_t t, size_t p) {
	tree[p] = tree[left(p)] + tree[right(p)];
}

区间修改 (加)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


template<typename T>
auto SegmentTree::add(const T& val, size_t l, size_t r, size_t s, size_t t, size_t p) -> void {
	if (l <= s && t <= r) {
		lazy[p] += val;
		tree[p] += val * len(s, t);
		return ;
	}
	pushdown(s, t, p); // 涉及子区间, 必须先 pushdown 保证正确性
	auto m = mid(s, t);
	if (l <= m) add(val, l, r, s, m, left(p));
	if (m + 1 <= r) add(val, l, r, m + 1, t, right(p));
	pushup(s, t, p);
}

区间查询

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


template<typename T>
auto SegmentTree<T>::query(size_t l, size_t r, size_t s, size_t t, size_t p) -> T {
	if (l <= s && t <= r) return tree[p];
	pushdown(s, t, p);
	auto m = mid(s, t);
	T sum {};
	if (l <= m) sum += query(l, r, s, m, left(p));
	if (m + 1 <= r) sum += query(l, r, m + 1, t, right(p));
	return sum;
}

template<typename T>
auto SegmentTree<T>::query(size_t l, size_t r) -> T {
	return query_impl(l, r, 1, size(), 1); // 从根节点开始
}

TODO: 因为后续数据结构进阶内容蓝桥杯省赛不太重点考，所以先把图论补起来再回来从线段树啃起。。🔽 (@2024-12-31)