范围最小查询(平方根分解和稀疏表)


难度级别
经常问 亚马逊 Apple 谷歌
排列 段树

在范围最小查询问题中,我们给出了一个查询和一个整数 排列。 每个查询都包含该范围,作为每个范围的左索引和右索引。 给定的任务是确定该范围内所有数量的最小值。

使用案列

输入:

arr [] = {2}

查询= {(0,5),(1,4),(3,7)}

输出:

.

说明:

2是范围编号{2,5,8,6,13,9,XNUMX}中的最小值

5是范围编号{5,8,6,13}中的最小值

6是范围编号{6,13,9,7,10}中的最小值

范围最小查询(平方根分解和稀疏表)

算法

  1. 创建一个2D数组并进行构建。 为此,将0标记为th 每行的列作为其行索引值。
  2. 遍历数组,并检查在i,j-1处的查找数组的数组是否小于在i + 2处的查找数组的数组J-1,j-1,如果为true,则将i,j处的查找数组更新为i,j-1处的查找数组。
  3. 否则,将i,j处的查找数组更新为i + 2处的查找数组J-11一
  4. 对于每个给定的查询,获取查询的左右范围,获取对数的日志值right-left + 1,然后检查左侧的查找数组j是否小于右侧的查找数组– 2j + 1,j,然后返回该值作为在右边– 2处的查找数组j + 1,j。
  5. 打印返回值

范围最小查询的解释(平方根分解和稀疏表)

我们提供了一个整数数组和一个范围查询,我们要求在所有整数值中找出最小值并返回该值,为此我们将构建查找数组。 该解决方案仅需要n个空间的平方根,但会消耗sqrt(n)时间,而对于每个给定的查询,它将花费恒定的时间,但需要一个额外的空间。 我们将在其中提出的想法是确定大小为2的子数组中的所有可能的最小值j j可以升至n的对数。

我们将建立一个查询表,为此,我们将使用一个查询数组。 在构建循环数组时,对于每次对i的查找,j都保留从i到2的最小值。J。 在i,j处的查找数组将保存数组每个值的值索引。 在遍历数组时,我们将确定任何给定范围的可能大小的最小值,将其乘以2乘幂j。 因此,我们将能够找到给定范围内的可能值。

对于任何给定的范围查询,我们将使用范围,以2的幂为单位。我们将使用范围值来查找right-left + 1之差的对数。然后,我们将比较在j处查找的数组小于右数组– 2j + 1,j,如果发现条件为真,则在左侧查找返回数组的值,j,否则在右侧查找返回数组– 2j + 1,j。 这将是必需的答案。

实施

范围最小查询的C ++程序(平方根分解和稀疏表)

#include<iostream>
#include<math.h>

using namespace std;

#define MAX 500

int lookup[MAX][MAX];

struct Query
{
    int Left, Right;
};

void buildLookup(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        lookup[i][0] = i;
    for (int j=1; (1<<j)<=n; j++)
    {
        for (int i=0; (i+(1<<j)-1) < n; i++)
        {
            if (arr[lookup[i][j-1]] < arr[lookup[i + (1<<(j-1))][j-1]])
                lookup[i][j] = lookup[i][j-1];
            else
                lookup[i][j] = lookup[i + (1 << (j-1))][j-1];
        }
    }
}

int solveQuery(int arr[], int Left, int Right)
{
    int j = (int)log2(Right - Left + 1);

    if (arr[lookup[Left][j]] <= arr[lookup[Right - (1 << j) + 1][j]])
        return arr[lookup[Left][j]];

    else return arr[lookup[Right - (1<<j) + 1][j]];
}

void getMinimumNumber(int arr[], int n, Query q[], int m)
{
    for (int i = 0; i < m; i++)
    {
        int Left = q[i].Left, Right = q[i].Right;
        cout <<"Minimum value between ["<<Left<<", "<<Right<<"] is:"<< solveQuery(arr, Left, Right) << endl;
    }
}

int main()
{
    int a[] = {2,5,8,6,13,9,7,10};
    int n = sizeof(a)/sizeof(a[0]);
    Query q[] = {{0, 5}, {1, 4}, {3, 7}};
    int m = sizeof(q)/sizeof(q[0]);

    buildLookup(a, n);
    getMinimumNumber(a, n, q, m);
    return 0;
}
Minimum value between [0, 5] is:2
Minimum value between [1, 4] is:5
Minimum value between [3, 7] is:6

用于范围最小查询的Java程序(平方根分解和稀疏表)

class MinimumNumberQuery
{
    static int MAX = 500;

    static int [][]lookup = new int[MAX][MAX];

    static class Query
    {
        int Left, Right;

        public Query(int Left, int Right)
        {
            this.Left = Left;
            this.Right = Right;
        }
    }
    
    static void	buildLookup(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            lookup[i][0] = i;

        for (int j = 1; (1 << j) <= n; j++)
        {
            for (int i = 0; (i + (1 << j) - 1) < n; i++)
            {
                if (arr[lookup[i][j - 1]] < arr[lookup[i + (1 << (j - 1))][j - 1]])
                    lookup[i][j] = lookup[i][j - 1];
                else
                    lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];
            }
        }
    }
    
    static int solveQuery(int arr[], int Left, int Right)
    {
        int j = (int)Math.log(Right - Left + 1);

        if (arr[lookup[Left][j]] <= arr[lookup[Right - (1 << j) + 1][j]])
            return arr[lookup[Left][j]];

        else return arr[lookup[Right - (1<<j) + 1][j]];
    }
    
    static void getMinimumNumber(int arr[], int n, Query q[], int m)
    {
        for (int i = 0; i < m; i++)
        {
            int Left = q[i].Left, Right = q[i].Right;

            System.out.println("Minimum of [" + Left + ", " + Right +
                               "] is " + solveQuery(arr, Left, Right));
        }
    }
    
    public static void main(String[] args)
    {
        int arr[] = {2,5,8,6,13,9,7,10};
        int n = arr.length;
        Query q[] = {new Query(0, 5),
                  new Query(1, 4),
                  new Query(3, 7)
        };
        int m = q.length;

        buildLookup(arr, n);
        getMinimumNumber(arr, n, q, m);
    }
}
Minimum of [0, 5] is 2
Minimum of [1, 4] is 5
Minimum of [3, 7] is 6

复杂度分析

时间复杂度

O(n对数n) 哪里 “ n” 是数组中元素的数量。

空间复杂度

O(n对数n) 哪里 “ n” 是数组中元素的数量。

参考