浅谈倍增与ST表

2023-12-28 20:23:30

如果我们有一个长度为 n n n 的数组 a a a,现在有 q q q 次询问,每次询问区间 [ l , r ] [l,r] [l,r] 的最大值。应该怎么做? ( n , q ≤ 2 × 1 0 5 ) (n,q \leq 2 \times 10^5) (n,q2×105)

如果暴力,就是 Θ ( n 2 ) \Theta(n^2) Θ(n2) 的,显然行不通。这时,就要用到ST表。

ST表是一种基于倍增思想的数据结构,支持对于一个数组无修改、区间修询问的大部分操作。接下来讲解一下他的运行过程。

Part 1:预处理ST表

f [ i ] [ j ] f[i][j] f[i][j] 表示 a a a 数组区间 [ i , i + 2 j ) [i,i+2^j) [i,i+2j) 的最大值。此时,我们可以运用类似DP的思想计算:

  • 初始化: ? i ∈ [ 1 , n ] , f [ i ] [ 0 ] = a [ i ] \forall i \in [1,n],f[i][0]=a[i] ?i[1,n],f[i][0]=a[i]
  • 运算顺序:优先从小到大枚举 j j j i i i 的枚举顺序任意。
  • 状态转移方程: f [ i ] [ j ] = max ? ( f [ i ] [ j ? 1 ] , f [ i + 2 j ? 1 ] [ j ? 1 ] ) f[i][j]=\max(f[i][j-1],f[i+2^{j-1}][j-1]) f[i][j]=max(f[i][j?1],f[i+2j?1][j?1])

此时,时间复杂度与空间复杂度均为 Θ ( n log ? n ) \Theta(n \log n) Θ(nlogn)

Part 2:求询问

这里就运用了倍增思想。对于一个询问区间 [ l , r ] [l,r] [l,r],我们可以将他分成若干段,使得每段的长度都可以表示为 2 i 2^i 2i,这样再利用数组 f f f 就可以求出答案。


因此我们从大到小枚举 i i i ( i ≥ 0 ) (i\geq 0) (i0)

  • 如果 r ? l + 1 ≤ 2 i r-l+1 \leq 2^i r?l+12i,则 a n s = max ? ( a n s , f [ l ] [ i ] ) ans=\max(ans,f[l][i]) ans=max(ans,f[l][i]),随后 l → l + 2 i l \to l+2^i ll+2i
  • 否则什么也不做

最终我们能够得出答案。单次询问时间复杂度 Θ ( log ? n ) \Theta(\log n) Θ(logn)

例题:

洛谷 P3865 【模板】ST 表
洛谷 P2251 质量检测

总结:倍增十分巧妙的运用了一个数可以分解为多个2的k次方数的特性,而ST表则是运用了倍增思想从而做到快速求解区间询问问题。

文章来源:https://blog.csdn.net/BasketballChick/article/details/135246917
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。