st表一般的适用范围
a b区间可能有重叠部分但是并不影响a+b区间的答案能通过a区间的答案 b区间的答案 加工出来 那么这种问题就是一个可重复贡献问题
例如区间最最值（RMQ) 区间公约数但是 区间求和 显然是不可以的
再例如区间按位与 区间按位或ST表都能高效解决；
优劣：
RMQ问题可以用st表维护 也可以用线段树
优势：时间复杂度 nlogn 单次查询o(1）代码量好写
劣势: 所需要的空间比较大维护的信息有限不支持修改操作
P4155 [SCOI2015] 国旗计划
时间限制: 1.50s 内存限制: 250.00MB
复制 Markdown 退出 IDE 模式
题目描述
A 国正在开展一项伟大的计划 —— 国旗计划。这项计划的内容是边防战士手举国旗环绕边境线奔袭一圈。这项计划需要多名边防战士以接力的形式共同完成，为此，国土安全局已经挑选了 N 名优秀的边防战士作为这项计划的候选人。
A 国幅员辽阔，边境线上设有 M 个边防站，顺时针编号 1 至 M。每名边防战士常驻两个边防站，并且善于在这两个边防站之间长途奔袭，我们称这两个边防站之间的路程是这个边防战士的奔袭区间。N 名边防战士都是精心挑选的，身体素质极佳，所以每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含。
现在，国土安全局局长希望知道，至少需要多少名边防战士，才能使得他们的奔袭区间覆盖全部的边境线，从而顺利地完成国旗计划。不仅如此，安全局局长还希望知道更详细的信息：对于每一名边防战士，在他必须参加国旗计划的前提下，至少需要多少名边防战士才能覆盖全部边境线，从而顺利地完成国旗计划。
输入格式
第一行，包含两个正整数 N,M，分别表示边防战士数量和边防站数量。
随后 N 行，每行包含两个正整数。其中第 i 行包含的两个正整数 Ci、Di 分别表示 i 号边防战士常驻的两个边防站编号，Ci 号边防站沿顺时针方向至 Di 号边防站为他的奔袭区间。数据保证整个边境线都是可被覆盖的。
输出格式
输出数据仅 1 行，需要包含 N 个正整数。其中，第 j 个正整数表示 j 号边防战士必须参加的前提下至少需要多少名边防战士才能顺利地完成国旗计划。
输入输出样例
输入 #1复制运行
4 8 2 5 4 7 6 1 7 3
输出 #1复制运行
3 3 4 3
说明/提示
N≤2×105,M<109,1≤Ci,Di≤M。
我们要选出第i条线段参与的情况下 覆盖一个环形的最少的线段数目
我们输入每条线段的编号和起点终点 然后按照起点排序
首先破环成链 后面复制一份 并且将每条线段在后侧都复制一份
设st表的定义为st[i][j]表示从编号为i的线段开始跳1<<j步最远能到达 的线段的编号
然后初始化st表 即每个编号跳一步能到哪也就是st[i][0]
dp的思想根据跳一步的数据 推导出2.....等二进制步数
然后最后开始跳 也就是模拟一遍过程 找到最少的线段数 跳的过程中 先设定一个目标 也就是总覆盖长度m+当前起点 然后优先跳大步子 逐渐减小 (倍增的思想） 因为每一步都是一个二进制某一位 从大到小跳一定可以表示所有的步数 每次枚举一个大步数 如果跳到的这个点小于终点 那么就跳转到这个点 并且答案加上这个步数 最后输出答案即可
#include <bits/stdc++.h> using namespace std; const int N=2e5+5; struct node{ int l,r,id; }line[2*N]; int n,m; int st[2*N][30]; int ans[N]; //输入 排序 复制 dp推导st 查询 bool cmp(node a,node b){ return a.l<b.l; } int jump(int i){ int aim=line[i].l+m,cur=i,nxt,ans=1; for(int p=20;p>=0;p--){ nxt=st[cur][p]; if(nxt!=0&&line[nxt].l<aim){ ans+=(1<<p); cur=nxt; } } return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>line[i].l>>line[i].r; line[i].id=i; if(line[i].l>line[i].r){ line[i].r+=m; } }sort(line+1,line+1+n,cmp); for(int i=1;i<=n;i++){ line[i+n]=line[i]; line[i+n].l+=m;line[i+n].r+=m; } for(int i=1,arrive=1;i<=2*n;i++){//初始化每个点一步最远跳到哪个边的编号的起点 while(arrive+1<=2*n&&line[arrive+1].l<=line[i].r){//某编号的边起点<自己的终点 arrive++; } st[i][0]=arrive; } for(int p=1;p<=20;p++){ for(int i=1;i<=2*n;i++){ st[i][p]=st[st[i][p-1]][p-1]; } } for(int i=1;i<=n;i++){ ans[line[i].id]=jump(i); } for(int i=1;i<=n;i++)cout<<ans[i]<<' '; return 0; }RMQ区间最值问题
P2880 [USACO07JAN] Balanced Lineup G
时间限制: 1.00s 内存限制: 512.00MB
复制 Markdown
中文
退出 IDE 模式
题目描述
每天，农夫 John 的 n (1≤n≤5×104) 头牛总是按同一序列排队。
有一天，John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。John 准备了 q (1≤q≤1.8×105) 个可能的牛的选择和所有牛的身高 hi (1≤hi≤106,1≤i≤n)。他想知道每一组里面最高和最低的牛的身高差。
输入格式
第一行两个数 n,q。
接下来 n 行，每行一个数 hi。
再接下来 q 行，每行两个整数 a 和 b，表示询问第 a 头牛到第 b 头牛里的最高和最低的牛的身高差。
输出格式
输出共 q 行，对于每一组询问，输出每一组中最高和最低的牛的身高差。
输入输出样例
输入 #1复制运行
6 3 1 7 3 4 2 5 1 5 4 6 2 2
输出 #1复制运行
6 3 0
st表分别维护最大值最小值 做差即可；
#include <bits/stdc++.h> using namespace std; const int N=5e4+5; int st1[N][30]; int st2[N][30]; int n,q; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q; int power=log(n)/log(2)+1; for(int i=1;i<=n;i++){ cin>>st1[i][0]; st2[i][0]=st1[i][0]; } for(int p=1;p<power;p++){ for(int i=1;i<=n-(1<<p)+1;i++){ st1[i][p]=max(st1[i][p-1],st1[i+(1<<(p-1))][p-1]); st2[i][p]=min(st2[i][p-1],st2[i+(1<<(p-1))][p-1]); } } while(q--){ int l,r;cin>>l>>r; int k=log(r-l+1)/log(2); int num1=max(st1[l][k],st1[r-(1<<k)+1][k]); int num2=min(st2[l][k],st2[r-(1<<k)+1][k]); cout<<num1-num2<<'\n'; } return 0; }区间GCD
P1890 gcd 区间
时间限制: 1.00s 内存限制: 125.00MB
复制 Markdown
中文
退出 IDE 模式
题目描述
给定 n 个正整数 a1,a2,…,an。
m 次询问，每次询问给定一个区间 [l,r]，输出 al,al+1,…,ar 的最大公因数。
输入格式
第一行两个整数 n,m。
第二行 n 个整数表示 a1,a2,…,an。
以下 m 行，每行两个整数 l,r 表示询问区间的左右端点。
输出格式
共 m 行，每行表示一个询问的答案。
输入输出样例
输入 #1复制运行
5 3 4 12 3 6 7 1 3 2 3 5 5
输出 #1复制运行
1 3 7
说明/提示
- 对于 30% 的数据，1≤n≤100，1≤m≤10；
- 对于 60% 的数据，1≤m≤1000；
- 对于 100% 的数据，1≤l≤r≤n≤1000，1≤m≤106，1≤ai≤109。
#include <bits/stdc++.h> using namespace std; const int N=1e3+5; int st[N][30]; int n,m; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++)cin>>st[i][0]; int t=log(n)/log(2)+1; for(int p=1;p<t;p++){ for(int i=1;i<=n-(1<<p)+1;i++){ st[i][p]=__gcd(st[i][p-1],st[i+(1<<(p-1))][p-1]); } } while(m--){ int l,r;cin>>l>>r; int k=log(r-l+1)/log(2); cout<<__gcd(st[l][k],st[r-(1<<(k))+1][k])<<'\n'; } return 0; }区间众数问题
题目描述： 给出一个非降序排列的整数数组a1,a2,…,an,你的任务是对于一系列询问i,j,回答ai,ai+1,…aj中出现次数最多的值所出现的次数
输入数据： 输入包含多组数据。每组数据第一行为两个整数n和q（1≤n，q≤100000）。第二行包含n个非降序排列的整数a1,a2,…,an（-100000≤ai≤100000）。以下q行每行包含两个整数i和j（1≤i≤j≤n），输入结束标志为n=0
输出格式 对于每个查询i，j，输出查询结果，也就是i~j中出现次数最多的数的个数，之间用换行隔开
注：朴素算法可能会超时！（这个注释原本题目里面就有，不是我自己加的。。）
由 @hicc0305 提供翻译
思路： 题目是升序排列的 那么我们可以对每一个数字建立一个桶 统计每个数字的次数
然后每次查询的时候 判断区间首末的元素类型是否相等 相等直接输出 不相等就特判以下首末元素的个数 然后将首末元素之间的元素的众数 用st表维护桶的区间最大值就可以 然后比较即可
所有相同的数都是连在一起的！！
所以我们可以把原序列分段，比如样例：-1 -1 1 1 1 1 3 10 10 10
我们可以这样记录：我们把所有相同的数归成一段。用num[p]来记录p这个位置在第几段里，比如num[1]=1,num[2]=1,num[3]=2。然后用l[i]来记录第i段的左边界的序号，r[i]来记录第i段的右边界的序号，比如l[2]=3,r[2]=6。
然后，我们对于每个询问l,r，只需要把l,r分成三个部分求，像这样：
