د سپین جدول په کارولو د سلسلو لنډ پوښتنې


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon د پبلیسس سیپینټ زو
پیشه

د سپیر میز میز ستونزې په کارولو سره د سلسلې مجموعې پوښتنې کې موږ د اندازې پوښتنې لرو او بشپړ عدد یې ورکړئ سور. ورکړل شوې دنده دا ده چې د ټولو انټرویو مجموعه ومومئ چې په لړ کې راځي.

بېلګه

تفتیش:

تیر [] = {1,4,6,8,2,5،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

پوښتنه: {(0 ، 3) ، (2 ، 4) ، (1 ، 5)

محصول:

19 16 25

وضاحت: د عددونو مجموعه چې د، ، range مجموعې سره په مجموع کې + + + + + + range کې راځي ، is 0 ده. یوځل بیا د بشپړو شمیرو مجموعه چې په، ، inc شمیره کې راځي په ټولیز ډول + + + + 3 1 is ده. د انډیجرونو مجموعه دا په 4 ، 6 رینج کې راځي په شمول د 8 + 19 + 2 + 4 + 6 8 ده.

د سپین جدول په کارولو د سلسلو لنډ پوښتنې

الګوریتم

  1. د 2d میټریکس په کارولو سره د وچو میز جوړ کړئ.
  2. د صف تیرول او د سپیر_ ټبل هر قطار په نښه کولو لپاره [i].
  3. په لنډ ډول د صف سربیره کړئ ، او د sparse_table ارزښت د تیر کالم د سپیر میز جدول په توګه او په sparse_table کې [i + 2 تازه کړئ. j-1 ] [j-1] او په سپارس_ټبل [i] [j] کې یې ذخیره کړئ.
  4. د هرې پوښتنې حل کولو لپاره ، موږ کی left او ښی لاس ته راوړو ، د محصول ارزښت 0 ته وټاکئ.
  5. له 16 څخه تر 0 پورې صف ته ځیر شئ ، او وګورئ چې کی + + 2j -1 له مساوي مساوي څخه کم دی ، که ریښتیا وي ،
    1. د وینډوز ارزښت په sparse_table [کی [] [j] کې اضافه کړئ او رقم په محصول کې زیرمه کړئ.
    2. د کی left نه کی + ارزښت + 2 ته تازه کړئ
  6. د محصول ارزښت بیرته ورکړئ.

د سپیر میز په کارولو سره د سلسلې Sum پوښتنې لپاره توضیحات

یوه صف او پوښتنه ورکړل شوې. د ټولو انټرویو مجموعه ومومئ چې د پوښتنې په لړ کې راځي. موږ به د سپیر میز میز څخه کار واخلو. موږ به یو دقیق میز جوړ کړو. د سپیرس جدول د 2d میټریکس دی په کوم کې چې موږ یو څه عملیات ترسره کوو او ارزښتونه یې په یو سپین جدول کې ذخیره کوو.

د 2d اعلان کړئ میټرکس. موږ هر یو د یو لاک قطار حد او حد حد 16 16 کالمونه اخیستي دي. موږ په ځانګړي توګه دلته 2 شمیره غوره کړې ځکه چې وروسته به موږ داسې شمیره ترلاسه کړو چې له 5 څخه ځواک ته 16 لوړه شوې ، نو 1 به کافي وي. بیا وروسته به د سپیر میز میز جوړولو لومړي مرحلې ته ورسیږو. موږ د سپس میز کې ارزښتونه د ورکړل شوي سرې عنصر په توګه په نښه کولو یا تازه کولو کې ځو په داسې حال کې چې د صف څخه تیریږي. بیا موږ ځړول شوي یو ، بیا به صف ته لاړ شو ، بیا به د قطار شمیره. په I ، j کې د سپیر میز جدول په i ، j-2 او د Iars XNUMX کې د کریسي میز جدول په توګه تازه کړئ.j-1، j-1. دا به د سپین میز لپاره وروستي اړین اوسمهال وي.

د هرې پوښتنې لپاره چې د کی left ، ښیې لړۍ په توګه ورکړل شوي وي ، موږ اړتیا لرو چې د صف څخه تیر شو ، مګر مخکې لدې چې د محصول ارزښت 0 ته وټاکئ نو له 16 څخه تر 0 پورې صف ته ځیر شئ ، ترڅو موږ وکولی شو هرځل د 2 شرایطو سره سم واک ترلاسه کړو. 1 <

تطبیق

د سپاري جدول په کارولو سره د لړۍ Sum پوښتنې لپاره C ++ برنامه

#include<iostream>

using namespace std;

const int k = 16;

const int N = 1e5;

long long sparse_table[N][k + 1];

void SparseTable(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        sparse_table[i][0] = arr[i];

    for (int j = 1; j <= k; j++)
        for (int i = 0; i <= n - (1 << j); i++)
            sparse_table[i][j] = sparse_table[i][j - 1] +
                                 sparse_table[i + (1 << (j - 1))][j - 1];
}

long long solveQuery(int Left, int Right)
{
    long long output = 0;
    for (int j = k; j >= 0; j--)
    {
        if (Left + (1 << j) - 1 <= Right)
        {
            output = output + sparse_table[Left][j];

            Left += 1 << j;
        }
    }
    return output;
}

int main()
{
    int arr[] = { 1,4,6,8,2,5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    SparseTable(arr, n);

    cout << solveQuery(0, 3) << endl;
    cout << solveQuery(2, 4) << endl;
    cout << solveQuery(1, 5) << endl;

    return 0;
}
19
16
25

د سپیر میز په کارولو سره د حد Sum پوښتنې لپاره د جاوا برنامې

class SumQueryRange
{
    static int k = 16;

    static int N = 100000;

    static long sparse_table[][] = new long[N][k + 1];

    static void SparseTable(int arr[],int n)
    {
        for (int i = 0; i < n; i++)
            sparse_table[i][0] = arr[i];

        for (int j = 1; j <= k; j++)
            for (int i = 0; i <= n - (1 << j); i++)
                sparse_table[i][j] = sparse_table[i][j - 1] + sparse_table[i + (1 << (j - 1))][j - 1];
    }
    
    static long solveQuery(int Left, int Right)
    {
        long sol = 0;
        for (int j = k; j >= 0; j--)
        {
            if (Left + (1 << j) - 1 <= Right)
            {
                sol = sol + sparse_table[Left][j];

                Left += 1 << j;
            }
        }
        return sol;
    }
    
    public static void main(String args[])
    {
        int arr[] = { 1,4,6,8,2,5};
        int n = arr.length;

        SparseTable(arr, n);

        System.out.println(solveQuery(0, 3));
        System.out.println(solveQuery(2, 4));
        System.out.println(solveQuery(1, 5));
    }
}
19
16
25

د پیچلتیا تحلیل

د وخت پیچلتیا

O (n * log (n)) هلته "n" په صف کې د عناصرو شمیر دی.

د ځای پیچلتیا

O (n * log (n)) هلته "n" په صف کې د عناصرو شمیر دی.

ماخذ