🌑

小羊儿的心情天空

Sparse Table

Feb 19, 2019 由 小羊

稀疏表,又称ST表,预处理 O(nlogn)O(n \log n),查询 O(1)O(1)

st[i][j] 表示在数组中,[i,i+2j1][i,i+2^j-1] 区间的最值。

当我们需要查询 [L,R][L,R] 的最值时,由于 RL+1R-L+1 可能不是正好 2j2^j 形式,那么我们可以考虑用某个 jj,查询 [L,L+2j1][L,L+2^j-1][R2j+1,R][R-2^j+1,R],并使这两个区间交叠。

int a[1010];
int st[1010][12];

void init(int n)
{
    for (int i = 0; i < n; i++)
        st[i][0] = a[i];
    for (int j = 1; (1<<j) <= n; j++)
        for (int i = 0; i+(1<<j)-1 < n; i++)
            st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}

int search(int l, int r)
{
    int k = int(log2(r-l+1.0));
    return min(st[l][k], st[r-(1<<k)+1][k]);
}

并且由代码可以看出,它还可以处理区间最大值/最值坐标等。