33DAI：批量导入三三文档

2026-05-20T18:24:01Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第50行：		第50行：
	[[Category:进阶算法]]		[[Category:进阶算法]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:16Z

导入1个版本

←上一版本	2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== ST表 ==

ST 表（Sparse Table）用于解决'''可重复贡献问题'''（如区间最值、区间 GCD），预处理 <math>O(n\log n)</math>，查询 <math>O(1)</math>，但不支持修改。

=== 原理 ===

使用倍增思想，<math>st[i][j]</math> 表示从 <math>i</math> 开始长度为 <math>2^j</math> 的区间的答案。

=== 建表 ===

<syntaxhighlight lang="cpp">
const int MAXN = 100005;
const int LOGN = 17; // floor(log2(MAXN))
int st[MAXN][LOGN + 1];

void build(int n)
{
for (int i = 1; i <= n; i++)
st[i][0] = a[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
</syntaxhighlight>

=== 区间查询 ===

<syntaxhighlight lang="cpp">
// 查询区间 [l, r] 的最大值
int query(int l, int r)
{
int k = log2(r - l + 1);
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
</syntaxhighlight>

=== 预计算 log2 ===

<syntaxhighlight lang="cpp">
int Log2[MAXN];
void pre_log2(int n)
{
Log2[1] = 0;
for (int i = 2; i <= n; i++)
Log2[i] = Log2[i / 2] + 1;
}
</syntaxhighlight>

[[Category:进阶算法]]
[[Category:三三文档]]

09-进阶算法/03-ST表 - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档