வேறுபாடு வரிசை | O (1) இல் வரம்பு புதுப்பிப்பு வினவல்


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது ஆர்சீசியம் கோட்நேஷன் டைரக்டி Expedia கூகிள் குவால்காம்
அணி வினவல் சிக்கல்

உங்களுக்கு ஒரு வழங்கப்படுகிறது முழு வரிசை மற்றும் இரண்டு வகையான வினவல்கள், ஒன்று கொடுக்கப்பட்ட எண்ணை ஒரு வரம்பில் சேர்ப்பது, மற்றொன்று முழு வரிசையையும் அச்சிடுவது. சிக்கல் “வேறுபாடு வரிசை | O (1) இல் உள்ள வரம்பு புதுப்பிப்பு வினவல் O (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 become ஆக மாறும்

பின்னர் முழு வரிசையையும் அச்சிடுவோம்.

20 30, 40 மற்றும் 25 இல் சேர்க்கப்படும், எனவே வரிசை {50, 60, 45, 50 become ஆக மாறும்

10 45 மற்றும் 50 இல் சேர்க்கப்படும், எனவே வரிசை {50, 60, 75, 80 become ஆக மாறும்

பின்னர் மீண்டும் முழு வரிசையையும் அச்சிடுவோம்.

வினவல்களைச் செய்தபின் இரண்டு செட் மதிப்புகள் அச்சிடப்படும்.

வேறுபாடு வரிசை | O (1) இல் வரம்பு புதுப்பிப்பு வினவல்

 

வேறுபாடு வரிசைக்கான வழிமுறை

  1. கொடுக்கப்பட்ட வரிசைக்கு சமமான அளவிலான வரிசையை உருவாக்கவும்.
  2. கொடுக்கப்பட்ட வரிசையின் முதல் உறுப்பு என முதல் குறியீட்டையும், கடைசி குறியீட்டை 0 உடன் துவக்கவும். மற்ற அனைத்து குறியீடுகளும் தற்போதைய மற்றும் முந்தைய உறுப்புகளின் வேறுபாட்டால் நிரப்பப்படுகின்றன.
  3. ஒவ்வொரு புதுப்பிப்பு வினவலுக்கும், உருவாக்கிய வரிசையின் கொடுக்கப்பட்ட இடது குறியீட்டில் எக்ஸ் மதிப்பைச் சேர்த்து, உருவாக்கிய வரிசையின் வலது குறியீட்டிலிருந்து எக்ஸ் கழிக்கவும்.
  4. ஒவ்வொரு அச்சு வினவலுக்கும், முதலில் A [i] = D [i] + A [i-1] சூத்திரத்தைப் பயன்படுத்தி உள்ளீட்டு வரிசையை நிரப்புகிறோம். பின்னர் மதிப்புகளை அச்சிடுங்கள்.

விளக்கம்

ஒரு வரிசை மற்றும் ஒரு எண் மற்றும் இரண்டு வகையான வினவல்கள் கொடுக்கப்பட்டுள்ளன. எனவே இரண்டு வகையான வினவல்களை நாம் செய்ய வேண்டும். எக்ஸ் எண்ணுடன் ஒரு வரம்பைக் குறிக்கும் இரண்டு எண்கள் எங்களிடம் இருக்கும். எனவே, கொடுக்கப்பட்ட வரம்பிற்கு இடையில் உள்ள அனைத்து குறியீடுகளிலும் எக்ஸ் எண்ணைச் சேர்ப்பதே எங்கள் பணி. ஒரு முறை ஒரு அப்பாவியாக அணுகுமுறையைப் பயன்படுத்தலாம். அதற்காக, ஒவ்வொரு முறையும் நாம் மதிப்புகளைப் புதுப்பிக்க வேண்டிய போதெல்லாம் கொடுக்கப்பட்ட வரிசையை கடந்து செல்லுங்கள்.

ஒரு சிறந்த தீர்வு இங்கே விவாதிக்கப்படுகிறது, இது வித்தியாசத்தை சேமிக்கும் கூடுதல் வரிசையை உருவாக்குவதாகும். அதனால்தான் இது ஒரு வித்தியாச வரிசை என்று அழைக்கப்படுகிறது. முதலில், உள்ளீட்டு வரிசையின் முதல் உறுப்பு என வேறுபாடு வரிசையின் முதல் உறுப்பை துவக்கவும். பின்னர் வேறுபாடு வரிசையின் கடைசி உறுப்பை 0 க்கு ஒதுக்கவும். அதன் பிறகு, நாம் வரிசை வழியாக பயணிக்கப் போகிறோம் மற்றும் தற்போதைய வரிசையில் உள்ள வேறுபாடு மற்றும் முந்தைய மதிப்பின் வித்தியாசத்தை தற்போதைய வரிசையில் தற்போதைய வரிசையில் சேமிக்கப் போகிறோம்.

புதுப்பிப்பு வினவலைப் பெற்றால், மதிப்புகளை ஒரு வரம்பாகப் பெறுவோம். எங்களுடன் ஒரு எண்ணும் வழங்கப்படுகிறது. வேறுபாடு வரிசையில் வரம்பின் இடது குறியீட்டில் அந்த எண்ணைச் சேர்க்கப் போகிறோம். இதேபோல் வேறுபாடு வரிசையின் வலது குறியீட்டிலிருந்து எக்ஸ் மதிப்பைக் கழிக்கவும். வரிசையை அச்சிடுவதற்கு நாம் வரிசை வழியாக பயணிப்போம், பூஜ்ஜிய குறியீட்டு மதிப்புக்கு கொடுக்கப்பட்ட வரிசையின் மதிப்பை நாம் உருவாக்கிய வரிசையாக புதுப்பிப்போம், இல்லையெனில் நாம் உருவாக்கிய வரிசையின் கூட்டுத்தொகையும் கொடுக்கப்பட்ட வரிசையின் முந்தைய மதிப்பும் கிடைக்கும் குறிப்பிட்ட குறியீட்டுக்கு அந்த மதிப்பை அச்சிடுக.

குறியீடு

வேறுபாடு வரிசைக்கு சி ++ இல் செயல்படுத்தல்

#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) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. கூடுதல் வேறுபாடு வரிசையை நாங்கள் உருவாக்கியதால், எங்களிடம் நேரியல் விண்வெளி சிக்கலானது.