अद्यतनांशिवाय श्रेणी बेरीज क्वेरी


अडचण पातळी सोपे
वारंवार विचारले काळा दगड जीई हेल्थकेअर मूनफ्रोग लॅब सारांश टॅक्सी 4 सुअर Twilio
अरे लार्सन आणि टुब्रो क्वेरी समस्या

समस्या विधान

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

उदाहरण

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

स्पष्टीकरण

श्रेणीमधील सर्व संख्यांची बेरीज (0, 4) सर्वसमावेशक 40 आहे आणि श्रेणी (1, 3) दरम्यान सर्व संख्यांची बेरीज समावेशित 24 आहे.

अद्यतनांशिवाय श्रेणी बेरीज क्वेरी

 

अल्गोरिदम

  1. दिलेल्या अ‍ॅरे प्रमाणे आकाराचा अ‍ॅरे अ‍ॅरे तयार करा.
  2. दिलेल्या अ‍ॅरेमधून जा आणि अ‍ॅरेच्या मागील घटकाची बेरीज आणि अ‍ॅरेचा वर्तमान घटक जोडून स्टोअर करा आणि त्यास अ‍ॅरेमध्ये संचयित करा.
  3. प्रत्येक क्वेरीसाठी, डावे 0 बरोबर असल्यास, नंतर अ‍ॅरे [उजवीकडे] परत करा,
  4. अन्यथा अ‍ॅरे [उजवीकडे] - बेरीज अ‍ॅरे [डावीकडे - 1] परत करा.

स्पष्टीकरण

आम्ही पूर्णांक आणि एक श्रेणी दिली आहे, आम्हाला प्रत्येक क्वेरीसाठी दिलेल्या श्रेणीतील सर्व घटकांची बेरीज शोधण्यास सांगितले गेले आहे. प्रत्येक क्वेरीमध्ये श्रेणीचा प्रारंभ आणि शेवटचा बिंदू म्हणून श्रेणी असते. या प्रश्नात कोणतीही अद्यतन क्वेरी गुंतलेली नाही. म्हणजेच क्वेरी उत्तर शोधताना कोणत्याही गोष्टी अद्यतनित करण्याची आवश्यकता नाही. आम्ही फक्त दिलेला अ‍ॅरे बनवू जेणेकरून 0 निर्देशांक पासून वर्तमान निर्देशांक पर्यंतच्या सर्व घटकांची बेल्ड अ‍ॅरेच्या आयथ स्थानावर असेल. अशा प्रकारे, प्रत्येक क्वेरी ओ (1) मध्ये ओ (एन) च्या अतिरिक्त जागेसह सोडविली जाईल.

आम्ही तयार केलेली बेरीज तयार करणार आहोत. या बेरीजमध्ये, 0 ते i पर्यंतच्या घटकांची बेरीज बेरीजच्या ith स्थितीवर ठेवली जाईल. आम्ही याची गणना करू कारण आम्ही बेरीजची पूर्वीची व्हॅल्यू आणि दिलेल्या अ‍ॅरेची सद्य व्हॅल्यू जोडू आणि ट्रॅव्हर्सिंग करताना सम अ‍ॅरेच्या वर्तमान निर्देशांक स्थितीमध्ये जमा करू. म्हणून जेव्हा एखाद्याने विचारले की या स्थानावरील सर्व संख्यांची बेरीज काय आहे, तेव्हा आम्हाला प्रत्येक अद्वितीय अ‍ॅरे घटकांसाठी त्या स्थानाचे मूल्य परत करणे आवश्यक आहे.

जेव्हा आम्हाला कोणतीही श्रेणी असलेली क्वेरी प्राप्त होईल आणि जर आपल्याला श्रेणीचा डावा किंवा प्रारंभ बिंदू 0 बरोबर असेल तर आपण नुकत्याच बेरीजच्या रकमेचे मूल्य [उजवीकडे] परत करूया, जे आपण वर चर्चा केले आहे तेच डावी श्रेणी आहे. 0 च्या बरोबरीचा नाही आम्ही बेरीज अ‍ॅरे [उजवीकडे] आणि बेरीज अ‍ॅरे [डावे -1] मधील फरक परत करू. त्यांना उत्तरे आवश्यक असतील. हा दृष्टिकोन आपण वापरत असलेल्या सोपा मार्गांपैकी एक आहे डायनॅमिक प्रोग्रामिंग.

कोड

सी ++ रेंज बेरीज क्वेरींसाठी कोड अद्यतनांशिवाय

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

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

    return 0;
}
40
24

श्रेणीशिवाय क्वेरी अद्यतनांशिवाय जावा कोड

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

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

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

ओ (एन + क्यू),  कारण आम्हाला प्रत्येक क्वेरीसाठी बेरीज (अ‍ॅरे) मोजण्यासाठी ओ (एन) आणि नंतर ओ (1) वेळ आवश्यक आहे.

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

येथे दिलेल्या पध्दतीत, 0 ते i पर्यंत घटकांची बेरीज संचित करण्यासाठी आम्ही एक नवीन अ‍ॅरे सम अ‍ॅरे तयार केला आहे. अशा प्रकारे या दृष्टिकोनाची आवश्यकता आहे ओ (एन) जागा. परंतु आपण मूळ अ‍ॅरेमध्येही बदल करू शकतो. मग जागेची गुंतागुंत स्थिरतेपर्यंत कमी केली गेली असती.