Feb 19, 2019 由 小羊
稀疏表,又称ST表,预处理 ,查询
st[i][j]
表示在数组中, 区间的最值。
当我们需要查询 的最值时,由于 可能不是正好 形式,那么我们可以考虑用某个 ,查询 和 ,并使这两个区间交叠。
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]);
}
并且由代码可以看出,它还可以处理区间最大值/最值坐标等。