ACL｜通用「线段树」模板
2024-11-11 13:47:13
发布于：浙江
前言
像使用
std::vector一样，使用「线段树」。
本文将介绍 AC(AtCoder) Library 中提供的 segtree 模版。
本文最后提供的 Segtree.cpp 对源码进行了一定的修改使得其可以单独在每一份 cpp 代码中使用。
同时由于本文的线段树的结构与常规的使用递归实现的线段树，存在很大的不同，本文介绍的线段树「无递归」，效率很高。
下文在介绍操作的使用方式的同时将会逐步剖析其源码的实现。
阅读代码实现部分需要读者对「面向对象」，「模板」，「函数指针」有一定的了解，并且需要一定的数学基础，能够理解 「函数」 和一些「代数」的知识。
简介
本文将介绍一种高效的支持「单点修改」，「区间查询」以及「二分查找」的线段树。
这是一种用于幺半群 的数据结构，即满足以下性质的代数结构：
- 结合律：对于所有 ，
- 存在单位元 ：使得对于所有 ，
给定一个长度为 的数组 ，它可以在 的时间内处理以下操作。
- 更新一个元素的值
- 计算给定区间内所有元素的「积」
为了方便描述，在本文中我们假设 op 和 e 的时间复杂度为 常数。如果这些操作的时间复杂度为 ，那么本文中所有操作的时间复杂度将乘以 。
操作
1. 构造函数
(1) segtree<T, op, e> seg(int n)
(2) segtree<T, op, e> seg(std::vector<T> v)
- (1)：它会创建一个长度为
n的数组a，所有元素都被初始化为e()。 - (2)：它会创建一个长度为
n = v.size()的数组a，初始化为v。
应定义以下内容。
- 存储的元素类型
T - 二元操作
T op(T a, T b) - 单位元
T e()
限制：
复杂度：
例如，对于一个值域不超过 的，总共有 个元素的「区间最小值查询」的问题，我们可以用以下方式来定义：
int op(int a, int b) {return std::min(a, b);}
int e() {return (int)(1e9);}
Segtree<int, op, e> seg(10);
原理与代码实现
本文介绍的线段树，结构基于「完全二叉树」，所有操作不采用递归实现。
令 为线段树存储的元素的大小， 为 bit_ceil(n) 即不小于 的最小的 的非负整数次幂。
我们这里令 ，那么 。创建一个大小为 的数组 ，我们将真实的数组 中的数据存储在 ，如下图所示。
对于数组 保存以下数据：
- 保存数据为单位元 。
- 对于 每个 维护 。
- 对于 每个 保存原数组中的元素 。
- 对于 每个 保存数据为单位元 。
据此我们可以按照以下方式实现构造函数：
explicit Segtree(const std::vector<T> &v) : n(v.size()) {
size = 1; while (size < n) size *= 2;
log = __builtin_ctz(size);
d = std::vector<T>(size * 2, e());
for (int i = 0; i < n; ++i) d[size + i] = v[i];
for (int i = size - 1; i >= 1; --i)
update(i);
}
其中 update() 操作实现为：
void update(int k) {d[k] = op(d[k * 2], d[k * 2 + 1]);}
2. set
void seg.set(int p, T x)
将 a[p] 赋值为 。
限制：
复杂度：
- 。
原理与代码实现
由于上面完全二叉树的特殊性质，我们可以自底向上更新数组 。
void set(int p, T x) {
assert(0 <= p and p < n);
p += size;
d[p] = x;
for (int i = 1; i <= log; ++i) update(p >> i);
}
3. get
T seg.get(int p)
返回 a[p]。
限制：
复杂度：
- 。
原理与代码实现
直接访问 d[p + size] 即可。
T get(int p) const {
assert(0 <= p and p < n);
return d[p + size];
}
4. prod
T seg.prod(int l, int r)
返回数组区间 的「积」，即 op(a[l], ..., a[r - 1])，假定其满足幺半群的性质。
若 ，则返回 e()。
限制：
复杂度：。
原理与代码实现
根据以上线段树实现，对于 数组，我们有以下性质。
- 数组中下标为偶数的元素必定为左儿子；
- 除根节点以外，数组中下标为奇数的元素必定为右儿子；
- 。
我们可以将查询拆分成若干个 ，我们取这些 的「积」即可。
那么令 为查询区间左端点， 为查询区间的右端点，我们以完全二叉树的视角考虑 数组， 在树中对应的真实下标为 ，但不妨我们分别将其记为 ，称为「左」和「右」。
以树的深度考虑，从底到顶，不断缩小 和 的距离，不同深度选择相应的 ，直到 。
对于「左」，若 为偶数，那么显然 和 都处于区间查询范围内，那么我们便不需要取 ，而是直接跳到其父亲 ；若 为奇数，那么显然 已经取过，或者不在范围内，我们直接取 ，同时为了避免重复取值，我们可以令 从而使其跳过原来的父亲 。
对于「右」，若 为偶数，那么显然 和 都处于区间查询范围内，那么我们便不需要取 ，而是直接跳到其父亲 ；若 为奇数，那么显然 已经取过，或者不在范围内，我们直接取 ，同时为了避免重复取值，我们可以令 从而使其跳过原来的父亲 。
「左」和「右」每次检查完当前层的 是否选取之后，都跳到下一层。
因此我们可以按照以下步骤来选择数组 中的一些元素并求「积」：
- 令当前查询区间对应的左边界为 ，右边界为 ，所取结果为 内的「积」。
- 令 。
- 若 为奇数则取 ，并同时另 。
- 若 为奇数则取 ，并同时另 。
- 令 。
- 重复执行步骤 直到 。
我们以上述 的数组 $\tt{a} $为例，若查询 内所有元素的积。则在数组 中选取的元素有 ；我们只需要求 op(d[9], d[5], d[24]) 的结果即可。
T prod(int l, int r) const {
assert(0 <= l and l <= r and r <= n);
T sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
5. all_prod
T seg.all_prod()
返回数组中所有元素的「积」，即 op(a[0], ..., a[n - 1])，假定其满足幺半群的性质。
若 ，返回 e()。
复杂度：。
原理与代码实现
直接访问 d[1] 即可。
T all_prod() const {return d[1];}
6. max_right
(1) int seg.max_right<f>(int l)
(2) int seg.max_right<F>(int l, F f)
- (1)：在线段树上执行二分查找需要定义函数
bool f(T x)。 - (2)：需定义一个以
T为参数，返回类型为bool的函数对象。
它返回一个满足以下两个条件的下标 r：
r = l或f(op(a[l], a[l + 1], ..., a[r - 1])) = truer = n或f(op(a[l], a[l + 1], ..., a[r])) = false
如果 f 是单调的，那么这是满足 f(op(a[l], a[l + 1], ..., a[r - 1])) = true 的最大的 r。
限制：
- 如果以相同的参数调用
f，其应该返回相同的值，即f无副作用。 f(e()) = true
复杂度：
原理与代码实现
我们令 存储从 开始从左到右，统计的所有元素的「积」。
与区间查询类似，我们利用完全二叉树的性质，当 为左儿子时，让其不断向上。
若当前对应的 若满足 ，则向下查询，否则令 ，即跳过其父亲，继续向上查询，直到某一层的最后一个元素为止；
向下查询的过程中，先查询左儿子 是否满足 ，若为真，同样取左儿子的值，即 ，再向下查找， 否则不取左儿子的值；重复执行，直到树的最后一层结束。
template<class F>
int max_right(int l, F f) const {
assert(0 <= l and l <= n);
assert(f(e()));
if (l == n) return n;
l += size;
T sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = l * 2;
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l += 1;
}
}
return l - size;
}
sm = op(sm, d[l]);
l += 1;
} while ((l & -l) != l);
return n;
}
7. min_left
(1) int seg.min_left<f>(int r)
(2) int seg.min_left<F>(int r, F f)
它返回一个满足以下两个条件的下标 l：
l = r或f(op(a[l], a[l + 1], ..., a[r - 1])) = truel = 0或f(op(a[l - 1], a[l], ..., a[r - 1])) = false
如果 f 是单调的，那么这是满足 f(op(a[l], a[l + 1], ..., a[r - 1])) = true 的最小的 l。
限制：
- 如果以相同的参数调用
f，其应该返回相同的值，即f无副作用。 f(e()) = true
复杂度：
原理与代码实现
与 max_right 操作类似，先令 ，然后令 存储从 开始从右到左，统计的所有元素的「积」。
再利用完全二叉树的性质，当 为右儿子时且不为根时，让其不断向上。
若当前对应的 满足 ，则向下查询，否则令 ，跳过其父亲，继续向上查询，直到某一层的第一个元素为止；
向下查询的过程中，先查询右儿子 是否满足 ，若为真，同样取右儿子的值，即 ，再向下查找， 否则不取右儿子的值；重复执行，直到树的最后一层结束。
template<class F>
int min_left(int r, F f) const {
assert(0 <= r and r <= n);
assert(f(e()));
if (r == 0) return 0;
r += size;
T sm = e();
do {
r -= 1;
while (r > 1 and (r & 1)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = r * 2 + 1;
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r -= 1;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
Segtree.cpp
#if __cplusplus >= 201703L
template<class T, auto op, auto e>
#else
template<class T, T (*op)(T, T), T (*e)()>
#endif
class Segtree {
private:
int n, size, log;
std::vector<T> d;
void update(int k) {d[k] = op(d[k * 2], d[k * 2 + 1]);}
public:
Segtree() : Segtree(0) {}
explicit Segtree(int n) : Segtree(std::vector<T>(n, e())) {}
explicit Segtree(const std::vector<T> &v) : n(v.size()) {
size = 1; while (size < n) size *= 2;
log = __builtin_ctz(size);
d = std::vector<T>(size * 2, e());
for (int i = 0; i < n; ++i) d[size + i] = v[i];
for (int i = size - 1; i >= 1; --i)
update(i);
}
void set(int p, T x) {
assert(0 <= p and p < n);
p += size;
d[p] = x;
for (int i = 1; i <= log; ++i) update(p >> i);
}
T get(int p) const {
assert(0 <= p and p < n);
return d[p + size];
}
T prod(int l, int r) const {
assert(0 <= l and l <= r and r <= n);
T sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
T all_prod() const {return d[1];}
template<bool (*f)(T)>
int max_right(int l) const {
return max_right(l, [](T x) {return f(x);});
}
template<class F>
int max_right(int l, F f) const {
assert(0 <= l and l <= n);
assert(f(e()));
if (l == n) return n;
l += size;
T sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = l * 2;
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l += 1;
}
}
return l - size;
}
sm = op(sm, d[l]);
l += 1;
} while ((l & -l) != l);
return n;
}
template<bool (*f)(T)>
int min_left(int r) const {
return min_left(r, [](T x) {return f(x);});
}
template<class F>
int min_left(int r, F f) const {
assert(0 <= r and r <= n);
assert(f(e()));
if (r == 0) return 0;
r += size;
T sm = e();
do {
r -= 1;
while (r > 1 and (r & 1)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = r * 2 + 1;
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r -= 1;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
};
无递归好像只适用于单点修改
有帮助，赞一个