अंतर ऐरे | ओ (1) में रेंज अपडेट क्वेरी


कठिनाई स्तर कठिन
में अक्सर पूछा आर्सेनियम कोडेशन डायरेक्टी Expedia गूगल क्वालकॉम
ऐरे क्वेरी की समस्या

आपको एक दिया जाता है पूर्णांक सरणी और दो प्रकार के प्रश्न, एक को श्रेणी में दिए गए नंबर को जोड़ना है और दूसरे को पूरे एरे को प्रिंट करना है। समस्या "अंतर सरणी | ओ (1) में रेंज अपडेट क्वेरी हमें ओ (1) में रेंज अपडेट करने की आवश्यकता है।

उदाहरण

arr[] = {20, 30, 25, 50}

Update(0, 1, 10)

print()

update(0, 2, 20)

update(2, 3, 30)

print()
(30 40 25 50) (50 60 75 80)

व्याख्या

10 को 20 और 30 में जोड़ा जाएगा, इसलिए सरणी {30, 40, 25, 50} बन जाएगी

फिर हम पूरे ऐरे को प्रिंट करेंगे।

२० को ३०, ४०, और २५ में जोड़ा जाएगा, इसलिए सरणी {५०, ६०, ४५, ५०} हो जाएगी

10 को 45 और 50 में जोड़ा जाएगा, इसलिए सरणी {50, 60, 75, 80} बन जाएगी

फिर फिर से हम पूरे ऐरे को प्रिंट करेंगे।

प्रश्नों को करने के बाद मूल्यों के दो सेट मुद्रित किए जाएंगे।

अंतर ऐरे | ओ (1) में रेंज अपडेट क्वेरी

 

अंतर सरणी के लिए एल्गोरिथ्म

  1. दिए गए सरणी के समान आकार का एक सरणी बनाएं।
  2. दिए गए एरे के पहले तत्व के रूप में पहले इंडेक्स को इनिशियलाइज़ करें, और आखिरी इंडेक्स को 0. और अन्य सभी इंडेक्स में करंट और पिछले एलिमेंट के अंतर से भरा जाए।
  3. हर अपडेट क्वेरी के लिए, निर्मित एरे के दिए गए बाएं इंडेक्स में मान X जोड़ें और एक्स को बनाए गए एरे के दाहिने इंडेक्स से घटाएं।
  4. प्रत्येक प्रिंट क्वेरी के लिए, पहले हम सूत्र A [i] = D [i] + A [i-1] का उपयोग करके इनपुट सरणी को भरते हैं। फिर मूल्यों को प्रिंट करें।

व्याख्या

एक सरणी और एक नंबर और दो प्रकार के प्रश्नों को देखते हुए। इसलिए हमें दो प्रकार के प्रश्नों का निष्पादन करना होगा। हमारे पास एक संख्या के साथ एक संख्या का प्रतिनिधित्व करने वाले दो नंबर होंगे। इसलिए, हमारा कार्य दिए गए सीमा के बीच सभी सूचकांकों में संख्या X को जोड़ना है। तरीकों में से एक अनुभवहीन दृष्टिकोण का उपयोग किया जा सकता है। इसके लिए, हर बार जब भी हमें मूल्यों को अद्यतन करने की आवश्यकता होती है, तो दिए गए सरणी को पीछे छोड़ें।

एक बेहतर समाधान पर यहां चर्चा की गई है, जो एक अतिरिक्त सरणी बनाने के लिए है जो अंतर को संग्रहीत करता है। इसलिए इसे अंतर सरणी कहा जा रहा है। सबसे पहले, इनपुट सरणी के पहले तत्व के रूप में अंतर सरणी के पहले तत्व को इनिशियलाइज़ करें। फिर अंतर सरणी के अंतिम तत्व को 0. पर असाइन करें। उसके बाद, हम सरणी के माध्यम से पार करने जा रहे हैं और वर्तमान मूल्य के अंतर और पिछले मान को अंतर सरणी में वर्तमान सूचकांक में संग्रहीत करते हैं।

हम मानों को एक श्रेणी के रूप में प्राप्त करेंगे, यदि हमें एक अपडेट क्वेरी मिलेगी। साथ ही हमें एक नंबर भी दिया गया है। फिर हम उस संख्या को अंतर सरणी में सीमा के बाएं सूचकांक में जोड़ने जा रहे हैं। इसी प्रकार अंतर सरणी के सही सूचकांक से मान X को घटाएं। सरणी को प्रिंट करने के लिए हम सरणी के माध्यम से आगे बढ़ेंगे और शून्य इंडेक्स वैल्यू के लिए हम दिए गए एरे के मान को अपडेट करेंगे जैसा कि हमने बनाया है, वरना हमें निर्मित एरे का योग और दिए गए एरे का पिछला मान मिलेगा और उस मूल्य को विशेष सूचकांक के लिए प्रिंट करें।

कोड

अंतर सरणी के लिए C ++ में कार्यान्वयन

#include<iostream>

using namespace std;

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

static void update(int dummyArray[], int l, int r, int x)
{
    dummyArray[l] += x;
    dummyArray[r + 1] -= x;
}

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

        if (i == 0)
            arr[i] = dummyArray[i];
        else
            arr[i] = dummyArray[i] + arr[i - 1];

        cout<<arr[i] << " ";
    }

    cout<<endl;
}

int main()
{
    int arr[] = {20,30,25,50};
    int n = sizeof(arr)/sizeof(arr[0]);

    int dummyArray[n + 1];
    buildArray(arr, dummyArray, n);

    update(dummyArray, 0, 1, 10);
    printArray(arr, dummyArray, n);
    update(dummyArray, 0, 2, 20);
    update(dummyArray, 2, 3, 30);

    printArray(arr, dummyArray,n);
    return 0;
}
30 40 25 50
50 60 75 80

अंतर सरणी के लिए जावा में कार्यान्वयन

class differenceArray
{
    static void buildArray(int arr[], int dummyArray[])
    {

        int n = arr.length;

        dummyArray[0] = arr[0];
        dummyArray[n] = 0;
        for (int i = 1; i < n; i++)
            dummyArray[i] = arr[i] - arr[i - 1];
    }
    
    static void update(int dummyArray[], int left, int right, int x)
    {
        dummyArray[left] += x;
        dummyArray[right + 1] -= x;
    }
    
    static int printArray(int arr[], int dummyArray[])
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (i == 0)
                arr[i] = dummyArray[i];
            else
                arr[i] = dummyArray[i] + arr[i - 1];

            System.out.print(arr[i] + " ");
        }

        System.out.println();

        return 0;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {20, 30, 25, 50};
        int n = arr.length;
        int dummyArray[] = new int[n + 1];

        buildArray(arr, dummyArray);

        update(dummyArray, 0, 1, 10);
        printArray(arr, dummyArray);
        update(dummyArray, 0, 2, 20);
        update(dummyArray, 2, 3, 30);

        printArray(arr, dummyArray);
    }
}
30 40 25 50
50 60 75 80

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

समय जटिलता

O (q) जहां 'क्यू' अद्यतन क्वेरी के रूप में निष्पादित प्रिंट प्रश्नों की संख्या है ओ (1) समय है.

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

पर) जहां "N" सरणी में तत्वों की संख्या है। चूंकि हमने एक अतिरिक्त अंतर सरणी बनाई है, इसलिए हमारे पास रैखिक अंतरिक्ष जटिलता है।