稀疏表(Sparse Table)

助记：
  • st 数组 为 n * m 矩阵； n = len(nums), m = int(math.log(n, 2))+1
      • 长度为 m, 那么 j 最大取值为 m-1, 我们需要 2 **(m-1) 至少能覆盖一般的数组！
  • 状态转移 st[i][j] 和 查询 query(i, j) 都是 将区间等分两半的。

原理

Sparse Table 算法（以下简称 ST 算法）是用来解决以下问题的：
区间最值查询（Range Minimum / Maximum Query，简称 RMQ 问题）：对于长度为 n 的数组 array[]，回答若干询问 RMQ(array, i, j)(0≤i,j<n)，返回数组 array[i:j+1] 中下标在 i，j 之间的最小或最大值。
找一个区间最值，最简单的直接比较，复杂度是 ，所以如果查找次数很少，用 ST 算法没有意义。ST 算法的应用场景就是要对一个数串查询多次的情况。
算法的基本思想就是对串中所有可能的区间组合的最值用二维数组保存，也就是所谓的预处理，查询时直接通过数组下标获取，) 的时间。

预处理

下面采用动态规划来对数串进行预处理，也就是填充二维数组。
状态定义：设st[i][j] 表示子数组array[i:i+2**j]的最大（或者最小）值。（此即 DP 的状态，区间长度正好为 2**j）
初始化：很容易发现对于 0≤i<n，st[i][0]=nums[i]。（此即 DP 的初值）
状态转移：我们把 st[i][j] 所表示的区间平均分成两段，也就是：
即原先区间长度为 ， 平分为两段之后，各段长度均为
于是得到转移方程：
notion imagenotion image
# 建立数组
n = len(nums)
# logn 可以长一一两个，但是不能短了！！短了就不能覆盖 nums 数组了
logn = int(math.log(n, 2)) + 1
# st[i][j] 子数组 nums[i: i+2**j] 的最小值 
st = [ [0]*logn for _ in range(n) ]  

# 初始化
for i, x in enumerate(nums):
    st[i][0] = nums[i]
        
# 填充数组
for j in range(1, logn):
    for i in range(0, n):
				# 起点为 i, 长度为 2**j, 因此闭区间右端点为 i+2**j-1。右端点不能越界
        if i + 2**j - 1 < n:
            st[i][j] = min(st[i][j-1], st[i + 2**(j-1)][j-1])

查询

对于查询区间 [i,j] （闭区间），我们分成两部分，即下图的两个矩形，长度相等，大小等于  k = log2(j−i+1)。
notion imagenotion image
k  = int(math.log(j-i+1, 2))
res = min(st[i][k], st[j-2**k + 1][k])

代码

import math

def build_st(nums):
				# 建立数组
        n = len(nums)
        logn = int(math.log(n, 2)) + 1
        st = [ [0]*logn for _ in range(n) ]  
        # 初始化
        for i, x in enumerate(nums):
            st[i][0] = x
        
        # 填充数组
        for j in range(1, logn):
            for i in range(0, n):
                if i + 2**j - 1 < n:
                    st[i][j] = min(st[i][j-1], st[i + 2**(j-1)][j-1])

        return st
    
def query(st, i, j):
    """ i j 为 nums中闭区间
    """
    k  = int(math.log(j-i+1, 2))
    return min(st[i][k], st[j- 2**k + 1][k])


if __name__ == "__main__":
    array = [4, 2, 1, 5, 7, 3]

    st = build_st(array)
    query_list = [[3, 5], [0, 5], [0, 1]]

    for x in query_list:
        print(query(st, *x))

参考

[1] Sparse Table 算法 - 刘毅的个人博客 (ethsonliu.com)
[2] YouTube 讲解