1 概述

稀疏表（Sparse Table，ST）是一种用于高效解决 静态区间查询（Range Query） 问题的数据结构，主要用于 可重复贡献问题（Idempotent Range Queries），例如区间最小值（RMQ）、区间最小值（RMQ）、区间GCD等。其核心思想是 预处理+倍增思想，可以在 O(n log n) 预处理 和 O(1) 查询 的时间复杂度下完成操作。

最后建的表如下图所示：

2 实现原理

详见：一种比线段树还高效的区间算法
数据结构与算法_倍增思想（稀疏表：区间最值查询问题）