stc算法_st编程语言详解

一.RMQ问题的概念

RMQ（Range Minimum/Maximum Query）问题，简单说就是求区间最值问题，是求区间最大值或最小值，即范围最值问题，若是简单的单次询问或者是区间长度很短的询问，可以用暴力的方法来实现，但面对大数据的时候此方法必然超时，这里介绍Ｏ(nlogn)预处理，O(1)查询的ST算法。

二,st算法

ST算法(Sparse Table)是用于解决RMQ问题(区间最值问题)的一种强有力的工具。

它可以O(nlogn)预处理，O(1)查询最值，利用的是倍增的思想。

但是使用ST算法后就不能进行修改操作了。

st算法的主要思想就是将所求的区间化为两个小区间，这两个区间的长度正好是2的k次幂，总长度正好覆盖[l,r]，得到的结果就是所求答案。

首先要清楚为什么是分成两段，而不是3段，4段，首先分成两段的话更好写的，比那些处理3段以及n段更简单。在logn的时间复杂度下，以2为底或者以其他数为底的话，时间复杂度差距也不是那么明显，所以选择了分成两段，便于位运算以及其他方面的简便操作。

三,例题

1. #A. Balanced Lineup排队

Description

每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队.

有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在队列中位置连续的牛来进行比赛.

但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000).

他想知道每一组里面最高和最低的牛的身高差别.

注意: 在最大数据上, 输入和输出将占用大部分运行时间.

Format

Input

• 第一行: N 和 Q. * 第2..N+1行: 第i+1行是第i头牛的身高.

• 第N+2..N+Q+1行: 两个整数, A 和 B (1 <= A <= B <= N), 表示从A到B的所有牛.

Output

*第1..Q行: 所有询问的回答 (最高和最低的牛的身高差), 每行一个.

Samples

输入数据 1

6 3

1

7

3

4

2

5

1 5

4 6

2 2

输出数据 1

6

3

0

思路

这道题是一道RMQ模板题，它要求的是一段区间内的最大值和最小值之差，因此我们要建立两个RMQ预处理内容，分别处理最大值和最小值。

建一个mx[i][j]代表从i开始,长度为2^j的区间内的最大值,mn[i][j]代表从i开始,长度为2^j的区间内的最小值。

根据倍增思想，长度为2^j的区间可被分成两个长度为2^(j-1)的子区间，然后求两个子区间的最值即可。所以在预处理时将该区间从中间平均分成两部分(中间有重叠没关系,不影响求最值)，每一部分的元素个数恰好为2^j-1个，也就是说，状态转移方程为:

mx[j][i] = max(mx[j][i – 1],mx[j + s[i – 1]][i – 1])

mn[j][i] = min(mn[j][i – 1],mn[j + s[i – 1]][i – 1])

（s[i]代表2^i次方）

若F[i, j]表示[i, i+2^j-1]区间的最值，区间长度为2^j，则i和j的取值范围是多少呢？

若数组的长度为n，最大区间长度2^r≤n<2^(r+1)，则r=⌊log2n⌋，比如n=8时k=3，n=10时k=3。在程序中，r=log2(n),i从1~i<=r,j从1~s[i]+j-1<=n(因为i代表区间长度,j代表区间的开始位置)

预处理代码:

 void pre() { int r = log2(n); for(int i = 1; i <= r; i++) for(int j = 1; s[i] + j - 1 <= n; j++) { mx[j][i] = max(mx[j][i - 1],mx[j + s[i - 1]][i - 1]); mn[j][i] = min(mn[j][i - 1],mn[j + s[i - 1]][i - 1]); } }

预处理完后，就要开始查询了。

若查询[l,r]区间的最大和最小值，则首先计算k值，和前面的计算方法相同，区间长度为r-l+1，

2^k≤r-l+1<2^(k+1)，因此k=log2(r-l+1) 。

若查询区间的长度大于或等于2^k且小于2^(k+1)，则根据倍增思想，可以将查询区间分为两个查询区间，取两个区间的最值即可。两个区间分别为从l向后的2^k个数及从r向前的2^k个数，这两个区间可能有重叠，但对求最值没有影响。

查询代码:

 int f(int x,int y) { int r = log2(y - x + 1); int t1 = max(mx[x][r],mx[y - s[r] + 1][r]); int t2 = min(mn[x][r],mn[y - s[r] + 1][r]); return t1 - t2; }

整体代码

 #include<bits/stdc++.h> #define int long long using namespace std; int t,n,q,a[],mx[][20],mn[][20],s[],x,y; void pre() { int r = log2(n); for(int i = 1; i <= r; i++) for(int j = 1; s[i] + j - 1 <= n; j++) { mx[j][i] = max(mx[j][i - 1],mx[j + s[i - 1]][i - 1]); mn[j][i] = min(mn[j][i - 1],mn[j + s[i - 1]][i - 1]); } } int f(int x,int y) { int r = log2(y - x + 1); int t1 = max(mx[x][r],mx[y - s[r] + 1][r]);//最大 int t2 = min(mn[x][r],mn[y - s[r] + 1][r]);//最小 return t1 - t2;//差 } signed main() { s[0] = 1; for(int i = 1; i <= 20; i++) s[i] = s[i - 1] * 2;//s[i]代表2^i次方 scanf("%lld%lld",&n,&q); for(int i = 1; i <= n; i++) { scanf("%lld",&t); mx[i][0] = mn[i][0] = t;//初始化,从第i个位置向后延2^0位的最大值和最小值都是输入的第i个位置上的数 } pre();//预处理 for(int i = 1; i <= q; i++) { scanf("%lld%lld",&x,&y); printf("%lld\n",f(x,y));//查询 } return 0; }

2.#B. 静态区间

Description

给你N个数字a[1],a[2]……….a[n]

M次询问，每次给定一个区间[L,R]

求a[L]……a[R]的最大公约数

Format

Input

第一行给出数字N，M

第二行N个数字,其值<=1e9

接下来M对数字

N<=5e4

M<=1e5

Output

输出M个行，每行一个数字

Samples

输入数据 1

5 3

4 12 3 6 7

1 3

2 3

5 5

输出数据 1

1

3

7

思路

跟上面一题一模一样,只不过不用2个数组,保留mx[][]就行,并且把定义改成mx[i][j]代表从i开始,长度为2^j的区间内的最大公约数，最后再把所有max()改成__gcd(),就可以了。

代码

 #include<bits/stdc++.h> #define int long long using namespace std; int s[],n,q,a[],mx[][101],t,x,y; void f() { int r = log2(n); for(int i = 1;i <= r;i++) for(int j = 1;s[i] + j - 1 <= n;j++) { mx[j][i] = __gcd(mx[j][i - 1],mx[j + s[i - 1]][i - 1]); } } int ff(int x,int y) { int r = log2(y - x + 1); int t1 = __gcd(mx[x][r],mx[y - s[r] + 1][r]); return t1; } signed main() { s[0] = 1; for(int i = 1;i <= 15 ;i++) s[i] = s[i - 1] * 2; scanf("%lld%lld",&n,&q); for(int i = 1;i <= n;i++) { scanf("%lld",&t); mx[i][0] = mn[i][0] = t; } f(); for(int i = 1;i <= q;i++) { scanf("%lld%lld",&x,&y); printf("%lld\n",ff(x,y)); } return 0; }

结语

怎么样?听懂了吗？如果这篇文章您听懂了的话请留个赞再走吧,goodbye~