اسپارس ٽيبل استعمال ڪندي حد سومري جو سوال


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon پبلس سيپينٽ زو
ڪيريو

اسپارس ٽيبل جي مسئلي جو استعمال ڪندي اسان جي رينج جي سوال جي حد ۾ ۽ هڪ ٻڏي ڏني وئي آهي صف. ڏنل ڪم سڀني عدد جي مجموعي کي ڳولڻ آهي جيڪي حد ۾ اچن ٿا.

مثال

انٽرويو

arr [] = {1,4,6,8,2,5،XNUMX،XNUMX،XNUMX،XNUMX}

سوال: {(0، 3)، (2، 4)، (1، 5)}

پيداوار:

19 16 25

وضاحت: انٽيگرز جو مجموعو جيڪو حد 0 ۾ شامل آهي ، 3 مجموعي طور تي 1 + 4 + 6 + 8 آهي 19. وري ، عددن جو مجموعو 2 ، 4 ۾ شامل آهي 6 + 8 + 2 آهي 16. انٽيگرز جو مجموعو اها حد 1 ۾ اچي ٿي ، 5 خاص طور تي 4 + 6 + 8 + 2 + 5 25 آهي.

اسپارس ٽيبل استعمال ڪندي حد سومري جو سوال

الورورٿم

  1. 2 ڊي ميٽرڪس استعمال ڪندي اسپارس ٽيبل ٺاهيو.
  2. صف جي پيچراءِ ڪريو ۽ اسپار_ ٽيبل جي هر قطار کي قطار ڪيو وڃي [i].
  3. لڪير کي ترتيب سان ترتيب ڏيو ، ۽ قيمت واري اسپار_ ٽيبل کي اڳئين ڪالم جي خراب ٽيبل جي مجموعي ۽ اسپار_ ميز تي جيترو تازه ڪاري ڪريو [i + 2 j- 1 ] [j-1] ۽ ان کي اسپار_بل ٽيبل تي محفوظ ڪريو [i] [j].
  4. هر سوال کي حل ڪرڻ لاءِ ، اسان کاٻي ۽ سا getي طرف وڃون ٿا ، ٻاٽي جي قيمت کي 0 ڏانهن سيٽ ڪريو.
  5. 16 کان 0 تائين صف جو نشان لڳايو ، ۽ چيڪ ڪريو ته کاٻي + 2j -1 صحيح کان گهٽ آهي برابر صحيح ، جيڪڏهن صحيح آهي ،
    1. sparse_table [ٻا]] [j] ڏانهن ٻاھر جي قيمت شامل ڪريو ۽ رقم کي محصول ۾ ذخيرو ڪريو.
    2. کاٻي کان کاٻي + 2 جي قدر کي تازو ڪريو
  6. محصول جي قيمت واپس ڪريو.

اسپارس ٽيبل استعمال ڪندي رينج سم سوال جي وضاحت

ھڪڙي قطار ۽ ھڪڙي سوال ۾ ڏني وئي. ڳولا ڪريو سڀني صفن جو مجموعي جيڪو سوال جي حد ۾ اچي ٿو. اسان اسپارس ٽيبل تصور استعمال ڪندا سين. اسان ٺاهيندا آهيون هڪ اسپاربل ميز. اسپارر ٽيبل هڪ 2 ڊي ميٽرڪس آهي جنهن ۾ اسان ڪي آپريشن ڪرڻ وارا آهيون ۽ قدرن کي هڪ اسپيس ٽيبل ۾ محفوظ ڪيو وڃي ٿو.

2 ڊي قرار ڏيو ميٽرڪس. اسان هر هڪ لک قطرن جي حد ۽ وڌ ۾ وڌ 16 ڪالمن جي حد ورتي آهي. اسان خاص طور تي نمبر 16 هتي ورتو آهي ڇو ته ان کانپوءِ اسان هڪ نمبر حاصل ڪنداسين جيڪا 2 کان وڌي ويل پاور 5 تائين آهي ، تنهنڪري 16 ڪافي آهي. پوء اسپار ميز جي تعمير جي پهرين اسٽيج تي ويندو. اسان هيٺ ڏنل آرٽ عنصر کي گهٽ ۾ گهٽ عنصر طور نشان يا اپڊيٽ ڪرڻ وارا آهيون جئين صف جي ذريعي وڃڻ. تنهن کان پوءِ اسان صف کي پار ڪرڻ وارا آهيون ، ڪي وري قطارَ ​​جي ڪورس تائين. i ، j-1 تي تمام نن tableڙي ٽيبل جي مجموعي طور تي ، آئي ، ج 2 ۽ گهٽ جدول جي جدول تي I + XNUMX کي اپڊيٽ ڪريو.j- 1، جي 1. هن غير معمولي ميز لاءِ حتمي گهربل تجويز هوندي.

بائیں ، سا rangeي حد تائين ڏنل هر سوال لاءِ ، اسان کي قطار کي ڳولهڻ جي ضرورت آهي ، پر انهي کان پهريان محصول جي قيمت کي 0 کي ترتيب ڏيو. صف کي 16 کان 0 تائين اچو ، ته جيئن اسان کي طاقتون ملي سگهن ، 2 ، هر دفعي 1 <

تي عملدرآمد

اسپارس ٽيبل استعمال ڪندي رينج سم سوال لاءِ سي ++ پروگرام

#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

اسپارس ٽيبل استعمال ڪندي رينج سم ڪوري لاءِ جاوا پروگرام

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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين * لاگ (اين)) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.

خلائي پيچيدگي

اي (اين * لاگ (اين)) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.

حوالي