የልዩነት ድርድር | የ O (1) ውስጥ የዝማኔ ጥያቄ


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ አርሴሲየም የኮድ ቁጥር Directi Expedia google Qualcomm
ሰልፍ የጥያቄ ችግር

አንድ ተሰጥቶሃል ኢንቲጀር ደርድር እና ሁለት ዓይነት መጠይቆች ፣ አንደኛው በአንድ የተወሰነ ክልል ውስጥ አንድ ቁጥር ማከል ሲሆን ሁለተኛው ደግሞ መላውን ድርድር ለማተም ነው ፡፡ ችግሩ “የልዩነት ድርድር | የ O (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} ይሆናል

ከዚያ መላውን ድርድር እናተምበታለን።

20 ወደ 30 ፣ 40 እና 25 ይታከላል ፣ ስለሆነም ድርድሩ {50, 60, 45, 50} ይሆናል

10 ወደ 45 እና 50 ይታከላል ፣ ስለዚህ ድርድሩ {50, 60, 75, 80} ይሆናል

ከዚያ እንደገና መላውን ድርድር እናተምበታለን።

ጥያቄዎቹን ካከናወኑ በኋላ ሁለቱ የእሴቶች ስብስቦች ይታተማሉ።

የልዩነት ድርድር | የ O (1) ውስጥ የዝማኔ ጥያቄ

 

ለልዩነት ድርድር አልጎሪዝም

  1. ከተሰጠው ድርድር ጋር ተመሳሳይ መጠን ያለው ድርድር ይፍጠሩ።
  2. የመጀመሪያውን መረጃ ጠቋሚ እንደየድርድሩ የመጀመሪያ አካል እና የመጨረሻውን መረጃ ጠቋሚ በ 0. ይጀምሩ እና ሌሎች ሁሉም ማውጫዎች አሁን ባለው እና በቀደመው ንጥረ ነገር ልዩነት የተሞሉ ናቸው ፡፡
  3. ለእያንዳንዱ የዝማኔ ጥያቄ ፣ ከተፈጠረው ድርድር በተሰጠው የግራ መረጃ ጠቋሚ ላይ እሴቱን ኤክስ ያክሉ እና ከተፈጠረው ድርድር የቀኝ ማውጫ ላይ X ን ይቀንሱ
  4. ለእያንዳንዱ የህትመት ጥያቄ በመጀመሪያ A [i] = D [i] + A [i-1] የሚለውን ቀመር በመጠቀም የግብዓት ድርድርን እንሞላለን ፡፡ ከዚያ እሴቶቹን ያትሙ።

ማስረጃ

አንድ ድርድር እና ቁጥር እና ሁለት ዓይነት መጠይቆች ተሰጥቷል። ስለዚህ ሁለቱን ዓይነት መጠይቆች ማከናወን አለብን ፡፡ ከአንድ ቁጥር X ጋር አንድን ክልል የሚወክሉ ሁለት ቁጥሮች ይኖሩናል ፣ ስለሆነም የእኛ ተግባር በተጠቀሰው ክልል መካከል ባሉት ሁሉም አመልካቾች ላይ ቁጥር 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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ጥ) የት "Q" የዝማኔ ጥያቄ በሚወስድበት ጊዜ የሚከናወኑ የሕትመት ጥያቄዎች ብዛት ነው ኦ (1) ጊዜ.

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ተጨማሪ የልዩነት ድርድር ስለፈጠርን ፣ መስመራዊ የቦታ ውስብስብነት አለብን።