通俗易懂的博客

ST表是能够在o(nlgn)的预处理情况下，在o(1)的复杂度情况下来求一段区间的最小值和最大值，可以用来求重复贡献对问题答案没有影响的问题

为了减少时间复杂度，可以先预处理出lg2的数组，就不要每次都去用log函数

lg2[0] = -1 //方便求lg2循环数组
for(int i = 1; i <= n;i ++) lg2[i] = lg[i>>1] + 1;

然后再预处理每个区间的最大值和最小值

void init()
{
    // 数组下标从1开始
    for (int i = 1; i <= n; i++)f[i][0] = a[i];
    
    for (int j = 1; (1 << j) <= n; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
            f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
}

最后就是O(1)的时间复杂度去询问每个区间的最大值和最小值，它是用两个区间取覆盖询问的区间，求着两个区间的最大值就询问区间的最大值

int query(int l, int r)
{
    int k = lg2[r-l+1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}