稀疏表（sparse table），法学-社会学-社会学方法-数据分析，一种动态规划的方法，用来解决区间最值查询（range minimum/maximum query; RMQ）问题。RMQ问题即为求给定区间中的最值问题。例如，有头牛，对于第头牛，它的高度是；有次查询，每次查询给定一个区间，求第头牛到第头牛中最高的牛和最矮的牛高度相差多少。求解此类问题，最简单的算法为对每个数据都进行查询——，但在查询次数很多（）的情况下，该算法效率较低。此时需要使用稀疏表算法。此算法建表为，查询为。稀疏表算法分为预处理和查询两步。假设求某区间内的最小值：①使用动态规划编程（dynamic programming; DP）思想，用表示区间中的最小值（即从开始，长度为的区间最值查询）。可开辟一个数组专门保存的值。如，表示间的最小值。因可由和导出，而递推的初值（所有的都是已知的），可采用自下至上的算法递推地给出所有符合条件的的值。由此可见，稀疏表算法的空间复杂度为。②进行查询。假设要查询从到这一段的最小值，则需先求出一个最大的，使满足。将分成两个（部分重叠的）长度为的区间：及。