Sparse Table(稀疏表)

Sparse Table简称ST，用于对一组静态数据进行区间查询。

例如：

• RMQ：区间最大（最小）值
• RGQ：区间最大公因数

这两个问题都可以用线段树解决。但线段树的查询时间是O(logn)，ST可以在O(1)时间内完成查询。代价是是ST不能对数组进行动态维护，数组在查询之前就固定下来。因此，如果需要动态维护数组，用线段树；反之，用ST。

什么样的问题可以用ST解决？例如说，求区间最小值，我们可以先把一个区间分成两个小区间，两个小区间的的最小值就是大区间的最小值。最大公因数也同理，求一个大区间的最大公因数，先求两个小区间的最大公因数，再求这两个数的最大公因数就是大区间的最大公因数。类似这类问题都能用ST解决。形式化的，ST能解决的问题为：

• 求数组的某一区间S的某一性质F(S)，性质F满足：

  $$若{s_1}\cup {s_2}=S，则F(S)=F(F(s_1),F(s_2)).$$

  可以验证，min和gcd都满足以上要求。

  详细内容参照这篇文章算法笔记-CSDN博客](https://blog.csdn.net/narcissus2_/article/details/89423591))。

下面是代码（read函数是快速读入一个整数的函数，只是用来过洛谷的oj）。

#include <cmath>
#define N 100001
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int arr[N];
int dp[21][N];
int n;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  return x * f;
}
void init() {
  int s = log2(n);
  for (int i = 1; i <= s; i++) {
    for (int j = 0; j <= n - (1 << i); j++) {
      dp[i][j] = gcd(dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))]);
    }
  }
}
int query(int l, int r) {
  int k = log2(r - l + 1);
  return gcd(dp[k][l], dp[k][r - (1 << k) + 1]);
}
int main() {
  int m;
  n = read();
  m = read();
  for (int i = 0; i < n; i++) {
    dp[0][i] = read();
  }
  init();
  int l, r;
  for (int i = 0; i < m; i++) {
    l = read();
    r = read();
    printf("%d\n", query(l - 1, r - 1));
  }
}