stc算法_st编程语言详解

stc算法_st编程语言详解ST算法解决BMQ问题详解(图文并茂,保证看懂)_rmq代码c++思路及模板

一.RMQ问题的概念

RMQ(Range Minimum/Maximum Query)问题,简单说就是求区间最值问题,是求区间最大值最小值,即范围最值问题,若是简单的单次询问或者是区间长度很短的询问,可以用暴力的方法来实现,但面对大数据的时候此方法必然超时,这里介绍O(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的区间内的最小值

stc算法_st编程语言详解

根据倍增思想长度为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~

stc算法_st编程语言详解

今天的文章
stc算法_st编程语言详解分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/80539.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注