آرایه تفاوت | پرس و جو به روزرسانی محدوده در O (1)


سطح دشواری سخت
اغلب در ارسیسیوم CodeNation دیرتی 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} تبدیل می شود

سپس کل آرایه را چاپ خواهیم کرد.

20 به 30 ، 40 و 25 اضافه می شود ، بنابراین آرایه به {50 ، 60 ، 45 ، 50} تبدیل می شود

10 به 45 و 50 اضافه می شود ، بنابراین آرایه به {50 ، 60 ، 75 ، 80} تبدیل می شود

سپس دوباره کل آرایه را چاپ خواهیم کرد.

دو مجموعه مقادیر پس از انجام پرس و جو چاپ می شوند.

آرایه تفاوت | پرس و جو به روزرسانی محدوده در O (1)

 

الگوریتم آرایه تفاوت

  1. آرایه ای با همان اندازه آرایه داده شده ایجاد کنید.
  2. اولین شاخص را با توجه به عنصر اول آرایه ، و آخرین شاخص را با 0. شروع می کنیم و تمام شاخص های دیگر با اختلاف عنصر فعلی و قبلی پر می شوند.
  3. برای هر پرس و جو به روزرسانی ، مقدار X را به فهرست سمت چپ داده شده آرایه ایجاد شده اضافه کنید و 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

تحلیل پیچیدگی

پیچیدگی زمان

O (q) جایی که "Q" تعداد درخواستهای چاپی است که به عنوان یک پرسش به روز رسانی انجام می شود O (1) زمان.

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است. از آنجا که ما یک آرایه اختلاف اضافی ایجاد کردیم ، پیچیدگی فضای خطی داریم.