범위 최소 쿼리 (제곱근 분해 및 희소 테이블)


난이도 하드
자주 묻는 질문 아마존 Apple 구글
배열 세그먼트 트리

범위 최소 쿼리 문제에서 우리는 쿼리와 정수를 제공했습니다. 정렬. 각 쿼리에는 범위가 각 범위에 대한 왼쪽 및 오른쪽 인덱스로 포함됩니다. 주어진 작업은 범위 내에있는 모든 숫자의 최소값을 결정하는 것입니다.

입력:

arr [] = {2, 5, 8, 6, 13, 9, 7, 10}

쿼리 = {(0, 5), (1, 4), (3, 7)}

출력:

+2 5 6 XNUMX

설명 :

2는 범위 번호 {2, 5, 8, 6, 13, 9} 중 최소값입니다.

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, 참이면 i, j에서 조회 배열을 i, j-1에서 조회 배열로 업데이트합니다.
  3. 그렇지 않으면 i, j에서 조회 배열을 i + 2에서 조회 배열로 업데이트합니다.j-1, j-1
  4. 주어진 각 쿼리에 대해 쿼리의 왼쪽 및 오른쪽 범위를 가져오고, 오른쪽-왼쪽 + 1의 로그 값을 가져 와서 왼쪽에서 조회 배열 j가 오른쪽에서 조회 배열보다 작은 지 확인 – 2j +1, j, 오른쪽에서 조회 배열로 값을 반환 – 2j + 1, j.
  5. 반환 된 값 인쇄

범위 최소 쿼리에 대한 설명 (제곱근 분해 및 희소 테이블)

정수 배열과 범위 쿼리를 제공했으며 모든 정수 값 중에서 최소값을 찾아서 그 값을 반환하도록 요청했습니다. 룩업 배열을 만들 것입니다. 이 솔루션은 n 공간의 제곱근 만 필요하지만 sqrt (n) 시간을 소비하는 반면, 주어진 쿼리마다 일정한 시간이 걸리지 만 추가 공간이 필요합니다. 여기서 우리가 제시 할 아이디어는 크기 2의 하위 배열에서 가능한 모든 최소값을 결정하는 것입니다.j 여기서 j는 n의 로그까지 올라갈 수 있습니다.

조회 배열을 사용하기 위해 조회 테이블을 구축 할 것입니다. 루프를 구성 할 때 배열을 i에서 조회 할 때마다 j는 i에서 2까지의 값 범위 중 최소값을 유지합니다.J. i, j의 조회 배열은 배열의 각 값에있는 값의 인덱스를 보유합니다. 배열을 순회하는 동안 가능한 크기의 주어진 범위에 대한 최소값을 2 제곱 j로 결정합니다. 이로 인해 주어진 범위에서 가능한 값을 찾을 수 있습니다.

주어진 범위 쿼리에 대해 2의 거듭 제곱과 같이 범위를 사용합니다. 범위 값을 사용하여 오른쪽-왼쪽 + 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) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (n 로그 n) 어디에 "엔" 배열의 요소 수입니다.

참고