st表： 作者：王清楚 链接：https://ac.nowcoder.com/discuss/395376 来源：牛客网
ST 表（Sparse Table）实际上是一种动态规划的方法，或者说简单一点，是用统计的思想来解决问题，它主要用于求解区间最大/最下值问题（也可也用来求和或者其他的东西）。以求区间最大值为例，它的基本思想是：用 {f[i] [j]}f[i][j]维护从从i开始长度为 2^{j}2 j 的区间的最大值，例如 {f[1] [1]}f[1][1] 表示的是以1开始长度为2的区间的最大值， {f[1] [2]}f[1][2]表达的是以1开始长度为4的区间的最大值。我们可以看到 {j}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+2 j−1 ][j−1])，这样 {O(nlogn)}O(nlogn)的时间复杂度我们就可以维护出f数组。 知道了f数组我们怎么来求任意区间[l,r]的最大值呢？也很简单，我们用两个长度刚好大于(r-l+1)/2的区间拼起来就好了（一个左边界是l，一个右边界是r）`
void rmp_st(int n) //预处理ST表,数组中有n个元素 { for(int i = 1; i <= n; i++) f[i][0] = a[i]; int m = (int)(log((double)n) / log(2.0)); for(int j = 1; j <= m; j++)//先循环j再循环i，因为必须要把长度为1的区间都算出来了才能求长度为2的 for(int i = 1; i+(1<<j)-1 <= n; i++) f[i][j] = min(f[i][j-1], f[i+(1<<(j-12))][j-1]); } int rmp_find(int l, int r) //求区间 l 到 r 之间的最值 { int k = (int)(log(1.0 * (r-l+1)) / log(2.0)); return min(f[l][k], f[r-(1<<k)+1][k]); }st表入门题目：点我传送门
题解代码：
/** 题目描述：链接：https://ac.nowcoder.com/acm/contest/82/B 来源：牛客网 给你一个长为n的序列a和一个常数k 有m次询问，每次查询一个区间[l,r]内所有数最少分成多少个连续段，使得每段的和都 <= k 如果这一次查询无解，输出"Chtholly" */ #include<bits/stdc++.h> #include<cstdio> #define ll long long using namespace std; ll a[1000005]; int st[1000005][21]; ///st表,i代表起始位置,j代表i后第2^j次方个区间的位置 int main() { int n,m,k,la=0; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); a[i]+=a[i-1]; ///预处理前缀和 } /**头文件： #include <algorithm> 二分查找的函数有 3 个： lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。 upper_bound(起始地址，结束地址，要查找的数值) 返回的是 第一个大于待查找数值 出现的位置。 binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。 */ ///预处理每一个位置i的第一个满足条件的区间的地址 for(int i=1;i<=n;i++) st[i][0]=upper_bound(a+1,a+1+n,a[i-1]+k)-a; ///预处理结尾边界，防止死循环 for(int i=0;i<=20;i++) st[n+1][i]=n+1; ///预处理st表 for(int i=n;i>=1;i--) ///逆向寻找，先处理大的边界。 for(int j=1;j<=20;j++) ///先找到st[i][j-1]的位置，再从该位置向后找2^（j-1）个区间 st[i][j]=st[st[i][j-1]][j-1]; ///所以预处理公式如上 while(m--) { int l,r,ans=0; scanf("%d%d",&l,&r); for(int i=20;i>=0;i--) { if(st[l][i]<=r) ///如果找到符合条件的区间，更新ans和l的值。 ans+=(1<<i),l=st[l][i]; } ///如果最后找到的边界<=r，说明在区间[l,r]中存在大于k的数,导致st查询中断,此时输出Chtholly； ///否则输出ans+1（因为最后找到的区间st[l][0]虽然大于r,但是l<=r,故还存在一小部分,可以组成一个较小的区间,故输出ans+1） if(st[l][0]<=r) printf("Chtholly\n"); else printf("%d\n",ans+1); } return 0; }st表增强题目：点我传送门 讲解链接：点我传送门
题解代码：
#include<bits/stdc++.h> #include<cstdio> using namespace std; int a[200005],to[200005]; vector<int>ve[200005]; int st[200005][21],deep[200005]; void dfs(int now,int fa) { int x=fa; for(int i=20;i>=0;i--) if(st[x][i]&&a[st[x][i]]<=a[now]) x=st[x][i]; if(a[x]<=a[now]) st[now][0]=st[x][0]; else st[now][0]=x; for(int i=1;i<=20;i++) st[now][i]=st[st[now][i-1]][i-1]; deep[now]=deep[fa]+1; int len=ve[now].size(); for(int i=0;i<len;i++) { int to=ve[now][i]; if(to!=fa) dfs(to,now); } } int main() { int x,y,n,q,w; scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n+q;i++) ve[i].clear(); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); ve[x].push_back(y); ve[y].push_back(x); } for(int i=1+n;i<=n+q;i++) { scanf("%d%d%d",&x,&y,&a[i]); ve[i].push_back(x); ve[x].push_back(i); to[i-n]=y; } dfs(1,0); for(int i=1;i<=q;i++) { int ans=0,nn=n+i; for(int j=20;j>=0;j--) { if(deep[st[nn][j]]>=deep[to[i]]) { ans+=(1<<j); nn=st[nn][j]; } } printf("%d\n",ans); } return 0; }