Range Minimum Query (Square Root Decomposition နှင့် Sparse Table)


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ Apple Google
အခင်းအကျင်း အပိုင်း - သစ်ပင်

အနိမ့်ဆုံးစုံစမ်းမှုပြproblemနာတွင်ကျွန်ုပ်တို့သည်စုံစမ်းမှုနှင့်ကိန်းတစ်ခုပေးခဲ့သည် အခင်းအကျင်း။ မေးမြန်းချက်တစ်ခုစီသည်အကွာအဝေးတစ်ခုစီအတွက်ဘယ်ဘက်နှင့်ညာဘက်အညွှန်းကိန်းများဖြစ်သည်။ ပေးထားသောတာဝန်သည်အကွာအဝေးအတွင်းရှိနံပါတ်အားလုံး၏အနည်းဆုံးကိုဆုံးဖြတ်ရန်ဖြစ်သည်။

နမူနာ

input:

arr [] = {၁၊ ၂၊ ၃၊ ၄၊ ၅၊ ၆၊ ၇၊ ၈}

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

output:

2 5 6

ရှင်းလင်းချက်:

၂ သည်အကွာအဝေးနံပါတ်များအနက်အနည်းဆုံး {၂၊ ၅၊ ၈၊ ၆၊ ၁၃၊ ၉} \ t

5 သည်နံပါတ်များအနိမ့်ဆုံးဖြစ်သည်။ {5, 8, 6, 13}

၆ သည်နံပါတ်အနိမ့်ဆုံး {၆၊ ၁၃၊ ၉၊ ၇၊ ၁၀} ။

Range Minimum Query (Square Root Decomposition နှင့် Sparse Table)

algorithm

  1. 2D ခင်းကျင်းမှုတစ်ခုကိုတည်ဆောက်ပြီးတည်ဆောက်ပါ။ ထိုအတွက် 0 ကိုမှတ်ပါth ၎င်း၏အတန်းအညွှန်းကိန်းတန်ဖိုးအဖြစ်တိုင်းအတန်း၏ကော်လံ။
  2. Array ကိုဖြတ်ပြီး i, j-1 ရှိ lookup ခင်းကျင်း၏ခင်းကျင်းမှုသည် i + 2 ရှိရှာဖွေမှုခင်းကျင်းမှု၏ကျဉ်းမြောင်းသည်ကိုစစ်ဆေးပါ။ည -1, j-1, မှန်လျှင် i တွင် j ကိုကြည့်ပါ။
  3. ကျန်အနေဖြင့် i + 2 ရှိ lookup ခင်းကျင်းအဖြစ် i၊ j တွင်ရှာဖွေမှုခင်းကျင်းမှုကို update လုပ်ပါည -1, ည -1
  4. ပေးထားသောရှာဖွေမှုတစ်ခုစီအတွက်ဘယ်ဘက်နှင့်ညာအကွာအဝေးကိုရှာပါ။ log-right + 1 ၏ log value ကိုရယူပြီးဘယ်ဘက်ရှိ lookup ခင်းကျင်းမှုရှိမရှိစစ်ဆေးပါ၊ j သည်ညာဘက်ရှိရှာဖွေမှုခင်းကျင်းနှင့်ညီမျှသည် - 2j +1, j ပြီးနောက်တန်ဖိုးကိုညာဘက်ခြမ်းကြည့်ပါ - ၂j + 1, ည။
  5. ပြန်လာသောတန်ဖိုး print ထုတ်ပါ

Range Minimum Query (Square Root Decomposition နှင့်ကျဲဇယား) အတွက်ရှင်းလင်းချက်။

ကျွန်ုပ်တို့သည် integer array နှင့် range query ကိုပေးခဲ့ပြီး integer တန်ဖိုးအားလုံးတွင်အနိမ့်ဆုံးတန်ဖိုးကိုရှာ။ ထိုတန်ဖိုးကိုပြန်ပေးသည်။ ထိုကြောင့်ကျွန်ုပ်တို့သည် lookup array ကိုတည်ဆောက်မည်ဖြစ်သည်။ ဖြေရှင်းချက်သည် n space ၏စတုရန်းအမြစ်ကိုသာလိုအပ်သည်။ သို့သော် sqrt (n) အချိန်ကိုလိုလိမ့်မည်၊ သို့သော်ပေးထားသောစုံစမ်းမှုတစ်ခုစီအတွက်မူ၎င်းသည်စဉ်ဆက်မပြတ်အချိန်ကိုယူမည်၊ ဤအရာတွင်ကျွန်ုပ်တို့ရှေ့ဆက်သွားမည်ဟူသောအယူအဆသည် subarray အရွယ်အစား ၂ ရှိဖြစ်နိုင်ချေနိမ့်ဆုံးတန်ဖိုးများကိုဆုံးဖြတ်ရန်ဖြစ်သည်j ဘယ်မှာည၏ log သို့သွားနိုင်သည်။

ငါတို့က Lookup ဇယားတစ်ခုဆောက်လိမ့်မယ်။ i ကိုကြည့်ရှုခြင်းတစ်ခုစီအတွက် array ကိုကွင်းကွင်းတည်ဆောက်ရာတွင် j သည်အနည်းဆုံးတန်ဖိုးများမှ i မှ 2 အထိရှိသည်J။ i, j ရှိ lookup ခင်းသည်တန်ဖိုးများ၏အညွှန်းများကို array တစ်ခု၏တန်ဖိုးတစ်ခုစီတွင်ကိုင်ထားလိမ့်မည်။ ခင်းကျင်းမှုကိုဖြတ်သန်းသွားသောအခါ၊ ၂ သည်ပါဝါသို့မြှင့်လာသည်နှင့်အမျှပေးထားသောဖြစ်နိုင်သမျှအရွယ်အစားအတွက်အနည်းဆုံးတန်ဖိုးကိုဆုံးဖြတ်လိမ့်မည်။ ဒါကြောင့်ကျွန်တော်တို့ဟာပေးထားတဲ့အကွာအဝေးမှာဖြစ်နိုင်တဲ့တန်ဖိုးကိုရှာဖွေနိုင်ပါလိမ့်မယ်။

ပေးထားသော range query အတွက်၊ 2 ၏ power ၌ရှိသကဲ့သို့ range များကိုအသုံးပြုလိမ့်မည်။ ကျွန်ုပ်တို့သည်လက်ဝဲ၏ခြားနားချက်၏ log ကိုရှာရန် range တန်ဖိုးများကိုအသုံးပြုမည်ဖြစ်သည်။ ထိုအခါလက်ဝဲတွင် lookup ၏ array ကိုနှိုင်းယှဉ်မည်။ ညာဘက်ခြမ်းထက်သေးငယ်သည် - 1j + 1, j၊ အကယ်၍ အခြေအနေမှန်ကန်ကြောင်းတွေ့ရှိပါက၊ လက်ဝဲဘက်ရှာဖွေမှုရှိ array ၏တန်ဖိုးကိုပြန်ယူပါ။j + 1, ည။ ဤသည်လိုအပ်သောအဖြေဖြစ်လိမ့်မည်။

အကောင်အထည်ဖော်ရေး

Range Minimum Query (Square Root Decomposition နှင့် Sparse Table) အတွက် 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

Range Minimum Query (Java Root Decomposition and Sparse Table) အတွက် 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

ရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာခြင်း

အချိန်ရှုပ်ထွေး

အို (n log n) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (n log n) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။

အညွှန်း