ST 表

beyoursven · 2025-03-25 19:32:37 · 个人记录

ST 表

struct ST {
  int n, f[MAXL][MAXN];  // 将 2^i 维度写在 ST 表数组的第一维，常数比较小
  void init(int n, int a[]) {
    this->n = n;
    for (int i = 1; i <= n; i++) {
      f[0][i] = a[i];
    }
    for (int x = 1; x < MAXL; x++) {
      for (int i = 1; i + (1 << x) - 1 <= n; i++) {
        f[x][i] = max(f[x - 1][i], f[x - 1][i + (1 << x - 1)]);
      }
    }
  }
  // 要求运算满足结合律和幂等律
  // 幂等律：x op x = x
  // 时间复杂度：O(1)
  int query1(int l, int r) {
    int k = lg2[r - l + 1];
    return max(f[k][l], f[k][r - (1 << k) + 1]);
  }
  // 只要求运算满足结合律
  // 时间复杂度：O(log n)
  int query2(int l, int r) {
    int ans = 0, k = r - l + 1;
    for (int i = 0; i < MAXL; i++) {
      if (k >> i & 1) {
        ans = max(ans, f[i][l]);
        l += 1 << i;
      }
    }
  }
} T;

for (int i = 2; i <= n; i++) {
  lg2[i] = lg2[i >> 1] + 1;
}