ST表与RMQ问题

ST表思想用来解决区间最值查询问题。与线段树相比,ST表只支持离线问题,但是在经过$O(n \lg n)$的预处理之后,ST每次询问的复杂度是$O(1)$的,而线段树的询问是$O(\lg n)$的,所以ST适合解决规模更大的离线问题。

算法思想

关键的过程在于预处理。我们用$f[i][j]$表示从$i$开始长度为$2^j$的区间(即$[i, i + 2 ^ j – 1]$)中的最值。算法基于这样一个事实:$f[i][j] = \max (f[i][j – 1], f[i + 2^{j – 1}][j – 1])$。显然$f[i][0] = 0$。所以我们只需要预处理出这个$f[i][j]$数组,然后在查询时,取$s = \log_2{(r – l + 1)}$,则区间$[l,r]$中的最值则为$\max (f[l][s], f[r – 2^s + 1][s])$。

注意

  • 边界条件$i + 2 ^ j – 1 \leq n$
  • 估算$\log_2{n}$的最大值决定数组第二维的大小
  • 计算$\log_2 x$的时候可以利用$\lfloor \log_2 x \rfloor = \log_2 \lfloor \frac{x}{2} \rfloor + 1$(使用整数表示)

例题

Luogu P3865

链接:P3865 – ST表

POJ 3264

链接:3264 – Balanced Lineup

 

说点什么

avatar
50
  Subscribe  
提醒