अ‍ॅरे वर सतत टाईम रेंज जोडा  


अडचण पातळी सोपे
वारंवार विचारले कोडनेशन डीई शॉ डायरेक्टि यामध्ये Google
अरे डायनॅमिक प्रोग्रामिंग

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

उदाहरण  

arr[] = {0, 0, 0, 0, 0}

Query: {(0, 2, 50), (3, 4, 20), (1, 3, 30)}
50 80 80 50 20

स्पष्टीकरण

50 मध्ये अ‍ॅरे मध्ये 0 ते 2 जोडले जाईल, अ‍ॅरे बनतील {50, 50, 50, 0, 0}

20 मध्ये अ‍ॅरे मध्ये 3 ते 4 जोडले जाईल, अ‍ॅरे बनतील {50, 50, 50, 20, 20}

30 मध्ये अ‍ॅरे मध्ये 1 ते 3 जोडले जाईल, अ‍ॅरे बनतील {50, 80, 80, 80, 20}

अ‍ॅरे वर सतत टाईम रेंज जोडा

 

अल्गोरिदम  

  1. श्रेणीच्या प्रत्येक क्वेरीसाठी चरणांचे अनुसरण करा.
    1. अ‍ॅरेच्या डावीकडील निर्देशिकेत दिलेली व्हॅल्यू जोडा आणि ती स्वतःच साठवा.
    2. मूल्य उजवीकडे शेवटच्या अ‍ॅरे इंडेक्सच्या बरोबरीचे नसते का ते तपासा, नंतर दिलेली व्हॅल्यू अ‍ॅरेच्या उजवीकडील +1 स्थानावर वजा करा आणि ती स्वतःच संचयित करा.
  2. अ‍ॅरे प्रिंट करण्यापूर्वी अ‍ॅरे अ‍ॅरेमधून ट्रॅव्हस म्हणून अपडेट करा आणि मागील व सद्य व्हॅल्यू जोडा आणि त्या अ‍ॅरेच्या व्हॅल्यूमध्येच स्टोअर करा.
  3. अद्यतनानंतर, परिणामी अ‍ॅरे मुद्रित करा.

अ‍ॅरे वर सतत वेळ श्रेणीसाठी स्पष्टीकरण  

पूर्णांक अ‍ॅरे आणि जोडण्यासाठी संख्या दिली. आम्हाला क्वेरीची श्रेणी देखील देण्यात आली आहे. यामध्ये डावे म्हणून श्रेणीचा प्रारंभ बिंदू आणि श्रेणीचा शेवटचा बिंदू उजवीकडे आहे. आम्हाला दिलेल्या श्रेणीत दिलेली संख्या सर्व संभाव्य पूर्णांकासह जोडण्यास सांगितले गेले आहे. आणि शेवटी शेवटी अ‍ॅरे प्रिंट करा. यासाठी आम्ही व्यतिरिक्त कार्य अतिशय सुधारित मार्गाने पार पाडणार आहोत. अ‍ॅरेच्या डाव्या आणि उजव्या + 1 स्थानावरील दिलेल्या मूल्यासह अ‍ॅरे अनुक्रमणिका मूल्ये आणि अ‍ॅरे प्रिंटिंग करण्यापूर्वी भरू.

हे सुद्धा पहा
फरक अ‍ॅरे | ओ (1) मधील श्रेणी अद्यतन क्वेरी

डावी आणि उजवीकडील प्रत्येक क्वेरीसाठी आम्ही दिलेली व्हॅल्यू डावीकडील डावीकडील इंडेक्समध्ये समाविष्ट करणार आहोत. आणि योग्य मूल्यासाठी आपण अ‍ॅरेच्या शेवटच्या निर्देशांकाइतकीच व्हॅल्यू बरोबर नाही का ते तपासणार आहोत, जर दिलेली कंडिशन पूर्ण झाली तर आपण दिलेली व्हॅल्यू इंडेक्स अपडेट करणार आहोत, तर दिलेल्या वॅल्यू वजाबाकी करू. ofरेचा उजवा अनुक्रमणिका आणि त्या अ‍ॅरेच्या उजव्या स्थान अनुक्रमणिकेत संग्रहित करा. प्रत्येक क्वेरीसाठी आम्ही ही ऑपरेशन्स करणार आहोत.

आता आपल्याला अ‍ॅरे प्रिंट करावा लागेल, परंतु त्याआधी आपण आपली सर्व व्हॅल्यू अपडेट करणार आहोत. त्या व्यतिरिक्त केलेल्या ऑपरेशनमध्ये ती अपडेट करणे आवश्यक आहे. Updateरेचा शोध घेऊन अ‍ॅरे अद्यतनित करा आणि दिलेली अ‍ॅरेची वर्तमान व्हॅल्यू आणि मागील व्हॅल्यू जोडून ती अ‍ॅरेच्या सद्य स्थितीत संचित करा. नंतर आपण अ‍ॅरे प्रिंट करणार आहोत.

कोड  

अ‍ॅरे वर सतत वेळ श्रेणीसाठी ऑपरेशनसाठी सी ++ मध्ये अंमलबजावणी

#include<iostream>

using namespace std;

void update(int arr[], int N)
{
    for (int i = 1; i < N; i++)
        arr[i] += arr[i - 1];
}

void addOperation(int arr[], int N, int left, int right, int value)
{
    arr[left] += value;
    if (right != N - 1)
        arr[right + 1] -= value;
}

void printArray(int arr[], int N)
{
    update(arr, N);
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int N = 5;

    int arr[N] = {0};

    addOperation(arr, N, 0, 2, 50);
    addOperation(arr, N, 3, 4, 20);
    addOperation(arr, N, 1, 3, 30);

    printArray(arr, N);
    return 0;
}
50 80 80 50 20

अ‍ॅरे वर निरंतर टाईम रेंजसाठी जावा मध्ये अंमलबजावणी

class AddOperation
{
    static void update(int arr[], int N)
    {
        for (int i = 1; i < N; i++)
            arr[i] += arr[i - 1];
    }
    static void addOperation(int arr[], int N, int left, int right, int value)
    {
        arr[left] += value;
        if (right != N - 1)
            arr[right + 1] -= value;
    }
    static void printArray(int arr[], int N)
    {
        update(arr, N);

        for (int i = 0; i < N; i++)
            System.out.print(""+arr[i]+" ");
        System.out.print("\n");
    }
    public static void main (String[] args)
    {
        int N = 5;

        int arr[] = new int[N];

        addOperation(arr, N, 0, 2, 50);
        addOperation(arr, N, 3, 4, 20);
        addOperation(arr, N, 1, 3, 30);
        printArray(arr, N);
    }
}
50 80 80 50 20

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

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

ओ (एन + क्यू) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या आणि "प्रश्न" क्वेरींची संख्या आहे. कारण आम्ही डावीकडील निर्देशांकातील मूल्यात वाढ केली आहे आणि अ‍ॅरेच्या हद्दीत असल्यास ते +1 निर्देशांकावरील मूल्य कमी केले आहे.

हे सुद्धा पहा
परवानगी असलेल्या परवान्यांसह पॅलिंड्रोम तयार करण्यासाठी किमान अंतर्भूत माहिती

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

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