ST算法

RMQ问题

 RMQ(Range Minimum/Maximum Query),即区间最值查询。对于长度为n的数列arr,回答若干询问Q(i,j),返回数列arr中下标在i,j之间的最大/小值。如果只有一次询问,那一遍for就可以搞定,但是如果有多次询问就无法在很快的时间处理出来。

ST算法

 ST算法是一个在线算法,它可以在O(nlogn)时间内进行预处理,然后在O(1)的时间内回答每个查询,假设现在的数组为arr[] = {1,3,6,7,4,2,5,9},算法步骤如下:

一、预处理(以处理区间最小值为例)

 dpi表示从第i位开始连续2^j^个数(也就是到i+2^j^-1)中的最小值。例如dp2表示从第2个数开始,连续2个数的最小值,即3,6之间的最小值,即dp2=3,从dp数组的含义我们就知道,dpi=arr[i](下标均是从1开始),初值有了,剩下的就是状态转移方程。首先把dpi平均分成两段(因为一定是偶数个数字),从i到i+2^j-1^-1为一段,i+2^j-1^到i+2^j^-1为一段(每段长度都为2^j-1^)。假设i=1,j=3时就是1,3,6,7和4,2,5,9这两段。dpi就是这两段最大值的最大值。于是得到了状态转移方程式dpi = max(dpi,dpi+2^j-1^)

for(int i = 1;i <= n;i++)
    dp[i][0] = arr[i];
for(int j = 1;(1 << j) <= n;j++)
    for(int i = 1;i + (1 << j) - 1 <= n;i++)
        dp[i][j] = Math.min(dp[i][j-1],dp[i + (1<<(j - 1))][j-1]);
二、查询

 假设我们需要查询区间[L,R]中的最小值,令k=log~2~(R-L+1),则区间[L,R]的最小值res=min(dpL,dpR-(1<<k)+1),为什么这样就可以保证区间最值?dpL维护的是[L,L+2^k^-1],dpL[k]维护的是[R-2^k^+1,R],因此只要证明R-2^k^+1 ≤ l+2^k^-1即可,这里证明省略

int k = (int) (Math.log(r - l + 1) / Math.log(2));
int min = Math.min(dp_min[l][k],dp_min[r - (1 << k) + 1][k]);
举个栗子

 L=4,R=6,此时k=log~2~(R-L+1)=log~2~3=1,所以RMQ(4,6)=min(dp4,dp5)=min(4,2)=2,很容易看出来答案是正确的

题目链接:POJ3264

 ST算法板子题,用java的同学要注意的就是把你所有会的输入输出优化全用上,不然会TLE 2333....

import java.io.InputStreamReader;
import java.util.Scanner;

public class CF522A {
    final static int N = 50005;
    static int[][] dp_min = new int[N][25];
    static int[][] dp_max = new int[N][25];

    public static void main(String[] args) {
        Scanner cin = new Scanner(new InputStreamReader(System.in));
        int n = Integer.parseInt(cin.next());
        int m = Integer.parseInt(cin.next());        
        for(int i = 1;i <= n;i++) {
            int tmp = cin.nextInt();
            dp_min[i][0] = tmp;
            dp_max[i][0] = tmp;
        }
        //预处理
        for(int j = 1;(1 << j) <= n;j++)
            for(int i = 1;i + (1 << j) <= n + 1;i++) {
                dp_min[i][j] = Math.min(dp_min[i][j - 1],dp_min[i + (1 << j - 1)][j - 1]);//加减优先级高于位运算
                dp_max[i][j] = Math.max(dp_max[i][j - 1],dp_max[i + (1 << j - 1)][j - 1]);
            }
    
        while((m--) != 0) {
            int l = Integer.parseInt(cin.next());
            int r = Integer.parseInt(cin.next());
            int k = (int) (Math.log(r - l + 1) / Math.log(2));
            int min = Math.min(dp_min[l][k],dp_min[r - (1 << k) + 1][k]);
            int max = Math.max(dp_max[l][k],dp_max[r - (1 << k) + 1][k]);
            System.out.println(max - min);
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

重要通知!小编出新的Java练习题咯!!

正确答案 3月5号公布 一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是( )。 A. import ...

4445
来自专栏趣谈编程

Unicode与UTF-8的区别

要弄清Unicode与UTF-8的关系,我们还得从他们的来源说起,下来我们从刚开始的编码说起,直到Unicode的出现,我们就会感觉到他们之间的关系

1282
来自专栏blackheart的专栏

[C#3] 1-扩展方法

1.从DEMO开始 先看一个扩展方法的例子: 1 class Program 2 { 3 public static void Main(...

21810
来自专栏CDA数据分析师

算法和数据结构—— 查找和排序

本文为简书作者郑永欣原创,CDA数据分析师已获得授权 查找和排序都是程序设计中经常用到的算法。查找相对而言较为简单,不外乎顺序查找、二分查找、哈希表查找和二叉排...

2406
来自专栏前端吧啦吧啦

涨薪必备Javascript,快点放进小口袋!

1402
来自专栏用户2442861的专栏

JavaScript 正则表达式上——基本语法

JavaScript种正则表达式有两种定义方式,定义一个匹配类似 <%XXX%> 的字符串

671
来自专栏xx_Cc的学习总结专栏

iOS-正则表达式的简单使用

4277
来自专栏前端吧啦吧啦

涨薪必备Javascript,快点放进小口袋!

3137
来自专栏互联网开发者交流社区

Java逻辑

1464
来自专栏chenjx85的技术专栏

leetcode-179-Largest Number(理解规则,自定义cmp函数进行排序)

1、这道题给定一个vector,里面存放着int类型的非负整数,要求把这些非负整数拼起来,尽可能拼成一个最大的整数。

1843

扫码关注云+社区

领取腾讯云代金券