ST表(SparsepTable)-解决区间最值大/小问题RMQ

2023-12-24 16:00:14

1.引入

有n个数,【l,r】 找max,m次询问

9,3,1,7,5,6,0,8

【0,5】9? ?,【4,5】6? ?,【3,5】7

看上去比较简单,是因为人脑进行了扫描。

暴力法 --O(nm)

以下代码是不完整的,欢迎大家进行修正。

import java.util.Scanner;

public class ST表 {
    public static void main(String[] args) {
        int[] arr = {9, 3, 1, 7, 5, 6, 0, 8};
        int ans = 0, l = 0, r = 7;
        System.out.println("请输入下标范围:");
        Scanner sc = new Scanner(System.in);
        int s1 = sc.nextInt();
        int s2 = sc.nextInt();
        while (s1 <= s2) {
            for (int i = s1; i <= s2; i++) {
                if (arr[i] > arr[i + 1]) { // 注意:这里我改成了arr[i] > arr[i + 1],以找到最大的两个连续元素之和

                }
            }
            s1++;
        }
        System.out.println(ans);
    }
}

缺点:当m特别大的时候,会炸掉----》优化

2.ST算法

RMQ问题:给定长度为n的静态数列,做m次询问,每次给定L,R,查询区间[L,R]内的最值。

3.原理

一个大区间若能被两个小区间覆盖,那么大区间的最值等于两个小区间的最值

两个小区间有部分重合,重合不影响结果。

4.ST算法步骤

(1)把整个数列分为很多小区间,并提前计算出每个小区间的最值

(2)对任意一个区间最值查询,找到覆盖它的两个小区间,用小区间的最值算出答案

4.1.把数列按倍增分成小区间

第1组:长度为1的小区间,有n个小区间,每个小区间有1个元素

第2组:长度为2的小区间,有n个小区间,每个小区间有2个元素

第3组:长度为4的小区间,有n个小区间,每个小区间有4个元素

.........

共有logn组

4.2查询任意区间的最值

(1)以任意元素为起点,有长度为1,2,4,....的小区间

(2)以任意元素为终点,它前面也有长度为1,2,4,...的小区间

(3)把需要查询的区间[L,R]分为2个小区间,且这两个小区间属于同一个组

以L为起点的小区间

以R为终点的小区间

这两个西秋季首尾相接覆盖[L,R]

一次查询的计算复杂度是O(1)

5.ST算法的应用场合

(1)静态数组的查询

(2)极大的查询次数,每次查询只需要O(1)

(3)核心思想:“大区间被两个小区间覆盖,小区间的重复覆盖不影响结果”

文章来源:https://blog.csdn.net/qq_73886051/article/details/135180840
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。