Sparse Table

释义 Definition

Sparse table：一种用于静态数组的预处理数据结构，常用于高效回答区间查询（尤其是区间最小值/最大值 RMQ）。典型做法是预先存储长度为 \(2^k\) 的区间信息，使查询可在 \(O(1)\) 或 \(O(\log n)\) 内完成（取决于运算是否“幂等”，如 min/max/gcd）。

发音 Pronunciation

/spɑːrs ˈteɪbəl/

例句 Examples

I used a sparse table to answer range minimum queries quickly.
我用稀疏表来快速回答区间最小值查询。

After preprocessing the array with a sparse table, each RMQ can be answered in constant time by combining two overlapping power-of-two intervals.
用稀疏表对数组预处理后，每次 RMQ 都可以通过合并两个重叠的 2 的幂长度区间在常数时间内得到答案。

词源 Etymology

sparse 源自拉丁语 sparsus（“散开的、稀疏的”），强调“分布不密”。table 源自拉丁语 tabula（“板、表格”）。在算法语境中，sparse table 指“只在某些关键尺度（如 \(2^k\) 长度）上记录信息的表”，因此称为“稀疏表”。

相关词 Related Words

• Range Minimum Query
• Preprocessing
• Idempotent
• Segment Tree
• Fenwick Tree
• Binary Lifting
• Lowest Common Ancestor
• Query

文学与著作 Literary Works

• Competitive Programmer’s Handbook（Antti Laaksonen）：在区间查询/静态 RMQ 等章节中常讲到 sparse table。
• Guide to Competitive Programming（Antti Laaksonen）：介绍竞赛常用数据结构与技巧，包含稀疏表相关内容。
• Competitive Programming 系列（Steven & Felix Halim）：在数据结构与区间查询的竞赛实践部分常出现该术语与用法。