विरळ सारणीचा वापर करून श्रेणीची बेरीज


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन पब्लिसिस सेपिएंट Zoho
अरे

विरळ सारणी समस्येचा वापर करून श्रेणी योग क्वेरीमध्ये आमच्याकडे श्रेणी क्वेरी आहे आणि एक पूर्णांक दिला आहे अॅरे. दिलेली कार्ये म्हणजे श्रेणीमधील सर्व पूर्णांकांची बेरीज शोधणे.

उदाहरण

इनपुट:

अरे [] = {1,4,6,8,2,5}

क्वेरी: {(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] वर मूल्य sparse_table अद्यतनित करा. j-1 ] [जे -१] आणि ते विरळ_टेबल [i] [j] वर संचयित करा.
  4. प्रत्येक क्वेरीचे निराकरण करण्यासाठी, आपण डावे आणि उजवे प्राप्त करू आणि आउटपुटचे मूल्य 0 वर सेट करू.
  5. अ‍ॅरे 16 ते 0 पर्यंत जा आणि डावीकडे + 2 तपासाj -1 बरोबर बरोबर बरोबर पेक्षा बरोबर आहे, खरे असल्यास,
    1. आउटपुटचे मूल्य sparse_table [डावीकडे] [j] वर जोडा आणि बेरीज आउटपुटमध्ये संचयित करा.
    2. डावीकडून डावीकडे + 2 चे मूल्य अद्यतनित करा
  6. आउटपुटचे मूल्य परत करा.

विरळ सारणीचा वापर करून रेंज सम क्वेरीसाठी स्पष्टीकरण

अ‍ॅरे आणि क्वेरी दिली. क्वेरीमधील श्रेणीमधील सर्व पूर्णांकांची बेरीज शोधा. आम्ही विरळ टेबल संकल्पना वापरत आहोत. आम्ही विरळ टेबल बनवित आहोत. विरळ टेबल हे 2 डी मॅट्रिक्स आहे ज्यात आपण काही ऑपरेशन्स करणार आहोत आणि व्हॅल्यूज विरळ टेबलमध्ये संचयित करणार आहोत.

2 डी घोषित करा मॅट्रिक्स. आम्ही एक लाख पंक्तीची मर्यादा आणि कमाल 16 स्तंभ घेतले आहेत. आम्ही येथे विशेषतः 16 क्रमांक घेतला आहे कारण त्या नंतर आम्हाला एक संख्या मिळेल जो 2 पॉवर पर्यंत 5 पेक्षा जास्त आहे, म्हणून 16 पुरेसे आहे. त्यानंतर विरळ टेबल तयार करण्याच्या पहिल्या टप्प्यावर जाईल. अ‍ॅरेमधून फिरत असताना आम्ही विरळ टेबलवर दिलेली अ‍ॅरे घटक म्हणून मूल्ये चिन्हांकित किंवा अद्यतनित करणार आहोत. नंतर नेस्टेड आहोत, पुन्हा kरेच्या क्र पर्यंत जाऊ. I, j वर स्पार्स टेबलची बेरीज म्हणून i, j-1 आणि विरळ टेबल i + 2 वर अद्यतनित करा.j-1, जे -1. विरळ टेबलसाठी हे अंतिम आवश्यक अद्यतन असेल.

डावी, उजवी श्रेणी म्हणून दिलेल्या प्रत्येक क्वेरीसाठी आपल्याला अ‍ॅरे ओलांडणे आवश्यक आहे, परंतु त्याआधी आउटपुटचे मूल्य ० वर सेट केले जाणे आवश्यक आहे. १ 0 ते ० पर्यंत अ‍ॅरेचा आढावा घ्या, जेणेकरून प्रत्येक वेळी २ च्या दृष्टीने शक्ती मिळू शकतील. 16 <

अंमलबजावणी

विरळ सारणी वापरून श्रेणी सम क्वेरीसाठी सी ++ प्रोग्राम

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * लॉग (एन)) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

स्पेस कॉम्प्लेक्सिटी

ओ (एन * लॉग (एन)) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

संदर्भ