Низ разлика | Упит за ажурирање домета у О (1)


Ниво тешкоће Тежак
Често питани у Арцесиум ЦодеНатион Дирецти Екпедиа гоогле куалцомм
Ред Куери Проблем

Добија се цео број поредак и две врсте упита, један је додавање датог броја у опсег, а други за испис читавог низа. Проблем „Низ разлика | Упит за ажурирање домета у О (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}

Затим ћемо поново исписати читав низ.

Два скупа вредности ће се одштампати након извршавања упита.

Низ разлика | Упит за ажурирање домета у О (1)

 

Алгоритам за низ разлика

  1. Направите низ исте величине као и дати низ.
  2. Иницијализујте први индекс као први елемент датог низа, а последњи индекс са 0. А сви остали индекси су попуњени разликом тренутног и претходног елемента.
  3. За сваки упит за ажурирање додајте вредност Кс датом левом индексу креираног низа и одузмите Кс од десног индекса креираног низа.
  4. За сваки упит за штампу прво попуњавамо улазни низ користећи формулу А [и] = Д [и] + А [и-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

Анализа сложености

Сложеност времена

О (к) где "К" је број упита за штампу извршених у зависности од упита за ажурирање О (1) време.

Сложеност простора

Он) где „Н“ је број елемената у низу. Пошто смо креирали додатни низ разлика, имамо линеарну сложеност простора.