रेंज सार तालिका का उपयोग कर योग क्वेरी


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना पब्लिसिस सैपिएंट Zoho
ऐरे

विरल तालिका समस्या का उपयोग करते हुए सीमा योग क्वेरी में हमारे पास एक श्रेणी क्वेरी है और एक पूर्णांक दिया गया है सरणी। दिए गए कार्य को उन सभी पूर्णांकों का योग ज्ञात करना है जो सीमा में आते हैं।

उदाहरण

इनपुट:

arr [] = {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. 2d मैट्रिक्स का उपयोग करके एक विरल तालिका बनाएं।
  2. सरणी को पीछे छोड़ें और सरणी [i] के लिए sparse_table की प्रत्येक पंक्ति को चिह्नित करें।
  3. सरणी को नेस्ट्रेसी से पार करें, और पिछले स्तंभ के विरल तालिका के मूल्य के रूप में और sparse_table [i + 2] के मूल्य sparse_table को अपडेट करें j-1 ] [j-1] और इसे sparse_table [i] [j] पर स्टोर करें।
  4. हल करने के लिए प्रत्येक क्वेरी के लिए, हम बाएं और दाएं मिलते हैं, आउटपुट का मान 0 पर सेट करते हैं।
  5. सरणी को 16 से 0 तक पार करें, और जांचें कि बाएं + 2j -1 से कम के बराबर है, अगर सही है,
    1. आउटपुट का मूल्य sparse_table [लेफ्ट] [j] में जोड़ें और आउटपुट में योग को स्टोर करें।
    2. बाएँ से बाएँ + 2 का मान अद्यतन करें
  6. आउटपुट का मान लौटाएं।

स्पार्स टेबल का उपयोग करते हुए रेंज सम क्वेरी के लिए स्पष्टीकरण

एक सरणी और एक क्वेरी को देखते हुए। क्वेरी में एक सीमा के भीतर आने वाले सभी पूर्णांकों का योग ज्ञात कीजिए। हम विरल तालिका अवधारणा का उपयोग करेंगे। हम एक विरल तालिका का निर्माण करेंगे। विरल तालिका एक 2d मैट्रिक्स है जिसमें हम कुछ संचालन करने जा रहे हैं और स्पार्स तालिका में मानों को संग्रहीत करते हैं।

2d घोषित करें मैट्रिक्स। हमने एक लाख पंक्तियों और अधिकतम 16 स्तंभों की सीमा ली है। हमने विशेष रूप से यहां एक संख्या 16 ली है क्योंकि उसके बाद हमें एक संख्या मिलेगी जो कि शक्ति 2 से 5 से अधिक है, इसलिए 16 पर्याप्त है। तब के बाद एक विरल मेज के निर्माण के पहले चरण में मिल जाएगा। हम सरणी के माध्यम से ट्रैवर्स करते समय दिए गए सरणी तत्व के रूप में विरल तालिका में मानों को चिह्नित या अपडेट करने जा रहे हैं। फिर नेस्टेड हम आर पार करने जा रहे हैं, फिर से पंक्तियों की संख्या तक। I, j-1 पर विरल तालिका के योग के रूप में i, j पर स्पार्स तालिका को अपडेट करें और i + 2 पर विरल तालिकाj-1, जे -1। यह विरल तालिका के लिए अंतिम आवश्यक अपडेशन होगा।

बाएं, दाएं श्रेणी के रूप में दी गई प्रत्येक क्वेरी के लिए, हमें सरणी को पीछे करना होगा, लेकिन इससे पहले आउटपुट का मान 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

जटिलता विश्लेषण

समय जटिलता

ओ (एन * लॉग (एन)) जहां "N" सरणी में तत्वों की संख्या है।

अंतरिक्ष जटिलता

ओ (एन * लॉग (एन)) जहां "N" सरणी में तत्वों की संख्या है।

संदर्भ