[C++知识库]ST表初识（C++）

ST表:Sparse Table，稀疏表,一种数据结构，主要用来解决静态的区间最大/最小值问题。

主要思想：倍增思想。

在看ST表之前，先看一个问题：

在这个序列中找出区间【1,3】、【3,5】、【1,5】

max【1,3】= 4?

max【3,5】= 5

max【1,5】= 5

大家可以发现，在区间【1,3】中最大值是4，区间【3,5】中最大值是5，在整个区间【1,5】中最大值是5，max(a,b) = max(max(a,c), max(c,b)); （a<=c<=b）

这个性质我们称之为：可重复性贡献

如果我们单单通过这个倍增思想的话，每次询问的时间复杂度仍认为O（logn），显然这并没有得到优化。

但是基于以上性质再结合我们倍增的思想（每次前进2^i）,使用两个预处理过的区间来覆盖询问区间，时间复杂度就被降至O(1）。

首先：

令f(i,j)表示从a[i] 开始连续2^j个数的最大值，区间表示为[ i，2 ^ j - 1 ];

显然，f[ i , 0 ] = a[ i ];

第二维则表示：倍增时跳的步数（2 ^ j - 1），跨越的长度。

通过以上的分析，我们得到一个状态转化方程：

max[ l , r ]?= max( f [ l ] ,[r - 1 ]?, f [ l + ( 1 << ( r - 1 ) ] [ r - 1 ] );

?以上为预处理部分，获得各区间的最大值。

接下来我们考虑询问部分，根据转化方程，我们将询问区间[ l , r ] 分成两部分。

f[l, l+2^s-1] 和 f[r-(2^s)+1,r];?

s：前进的步数??

我们希望前一个子区间的右端点尽可能接近r。当l + 2 ^ s -1 =? r??时，有 s = log2( r - l + 1);

但因为s是整数，所以我们向下取整? ，根据上面“可重复贡献”的性质，重叠并不会对区间最大值产生影响。同时两个区间的并完全覆盖[ l , r ]?。

由于输入输出数据一般很多，防止因为I/O被卡，这里提供一个快速读入的函数：

inline int read() { 
  char c = getchar();
  int x = 0, f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}

?由于s 也就是log函数每次都需要计算，这里我们直接通过递推将log函数预处理出来

//由于log[1] = 0;若想通过下面的循环直接处理，需要将log[N] 初始化为 -1；
log[N] = {-1};

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

洛谷模板题：?https://www.luogu.com.cn/problem/P3865

#include <bits/stdc++.h>
using namespace std;
const int MAX = 2000010;
int f[MAX][50], logn[MAX]= {-1};

inline int read() { 
  char c = getchar();
  int x = 0, f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}

int main() {
  int n = read(), m = read();
  for (int i = 1; i <= n; i++)
  {
      f[i][0] = read();
      logn[i] = logn[i/2] + 1; //预处理log函数
  } 
  
  //预处理最大值
  for (int j = 1; j <= logn[n]; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); 


  while(m--) 
 {
    int x = read(), y = read();
    int s = logn[y - x + 1];
    printf("%d\n", max(f[x][s], f[y - (1 << s) + 1][s]));
  }
  return 0;
}

?代码中f [ MAX ][ 50 ],这里的50，也就是第二维，指的就是“跳跃”的步数，大小根据数据范围而定，不小于log[MAX];

最后我们来看一下ST表的时间复杂度：

预处理：O（nlogn）；

询问：O（1）；

时间复杂度：O（nlogn + m）；

?ST表优点：时间复杂度较低 、代码量较少；

ST表缺点：维护的信息有限，只支持静态操作（不支持修改操作）；