区间最值问题之ST表算法

区间最值问题之ST表算法

1.ST算法思想

ST(Sparse Table)算法是一种用于解决RMQ(Range Minimum/Maximum Query，即区间最值查询)问题的离线算法。

其中使用到了倍增思想，像vector这种内存容量不足之后翻倍分配就属于这种范畴，具体来说：任意一个数可以表示成若干个2次幂之和，例如：5，二进制表示为101 = 2^2 + 2^0，直接采用递推方式，每一步都需要计算，算法复杂度变高，而通过倍增我们可以进一步缩小求解范围。

ST算法描述：首先明确解决的是区间最值问题，那么对于给定的数组arr = [1,4,8,20, 10]，长度为2^j的区间可以拆分成两个2^(j-1)的区间，那么对于dp[i][j]，i表示区间起点，j表示区间长度为2^j,所代表的区间为[i, i + 2 ^ j]。递推公式为：

dp[i][j] = max(dp[i][j - 1], dp[i + 1 << (j - 1)][j - 1])

ST表涉及两个核心操作，分别是创建、查询。

创建

dp[i][j]表示从i开始长度为2^j的区间最值，那么i和j的取值需要明确。

对于数组arr长度为n,最大区间长度为2^k <= n < 2^(k+1)，则k=log(n)，这里log为以2为底向下取整。

创建过程分为以下两步：

1.预处理长度为1的区间

dp[i][0]表示从i开始，长度为2^0=1的区间，等于当前元素。

int n = input.size();
// 预处理每个区间的最值
int k = (int)(log((double)(n)) / log(2.0));
// 预处理区间长度等于1
for (int i = 1; i <= n; i++) {
  dp[i][0] = input[i - 1];
}

2.预处理长度大于1的区间

• j的取值范围为[1, k]
• i的取值范围为[1, n - (1 << j) + 1]

// 预处理区间长度大于1
for (int j = 1; j <= k; j++) {
  // 边界计算: [l, r] 最后一个i的起点 len = 2 ^ j = r - start + 1 -> start = n
  // - 2 ^j + 1
  for (int i = 1; i <= n - (1 << j) + 1; i++) {
    // 区间[i, i + 2^j]一分为二 2^j = 2^(j - 1)*2 分成两个j-1长度的区间
    dp[i][j] = max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
  }
}

过程分析,以数组[3, 12, 17, 8, 18, 10, 2, 9, 20]初始化为例，经过预处理之后的dp数组为：

图中箭头方向表示dp的转移过程。时间复杂度：o(nlogn)。

查询

有了预处理的ST表之后，可以以O(1)时间复杂度进行查询。

给定[l, r]，查询该区间的最大值/最小值，问题转化为从l向右覆盖2^k个数，从r向左覆盖2^k个数，一定覆盖整个区间[l, r]，虽然会有重复覆盖，但不影响结果。

int ST_Query(int l, int r) {
  // 2^k <= r - l + 1 < 2^(k + 1)
  int k = (int)(log((double)(r - l + 1)) / log(2.0));
  // 从l向右覆盖2^k个数,从r向左覆盖2^k个数 一定覆盖整个区间[l, r]
  // 会有重复覆盖,不影响结果
  return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}

期待您与我进行讨论!

本节完