Массив бойынша тұрақты уақыт диапазоны


Күрделілік дәрежесі оңай
Жиі кіреді CodeNation DE Шоу Directi Expedia Google
Array Динамикалық бағдарламалау

Сіз ан бүтін сан массив және бастапқыда ол 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 позициясында берілген мәнмен толтырамыз және осы массивті жаңартудан шығарар алдында.

Әрбір берілген сұраныс үшін солға және оңға біз берілген мәнді оң жақтың сол жақ индексіне қосамыз, тек сол жақ индексте есте сақтаңыз. Ал дұрыс мән үшін біз мән құқығы массивтің соңғы индексіне тең еместігін тексереміз, егер берілген шарт қанағаттандырылса, онда берілген мән индексін жаңартамыз, берілген мәнді алып тастаймыз жиымның оң индексі және оны массивтің дұрыс позиция индексінде сақтау керек. Әрбір сұраныс үшін біз осы әрекеттерді орындаймыз.

Енді біз массивті басып шығаруымыз керек, бірақ бұған дейін біз барлық мәндерді жаңартамыз, біз қосқан операция, біз оны жаңартуымыз керек. Сонымен, жиымнан өтіп, берілген массивтің ағымдағы мәнін және алдыңғы мәнін қосып, массивті жаңартыңыз және оны массивтің ағымдағы күйіне сақтаңыз. Содан кейін біз массивті басып шығарамыз.

код

Массивтегі тұрақты жұмыс уақытының диапазоны үшін C ++ бағдарламасында енгізу

#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

Java-да массивке қосылатын тұрақты уақыт аралығында жұмыс жасау

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

Күрделілікті талдау

Уақыттың күрделілігі

O (N + Q) қайда «N» - бұл массивтегі элементтер саны және «Q» - сұраныстар саны. Себебі біз сол жақтағы индексті жоғарылаттық және егер массивтің шекарасында болса, оң жақтағы + 1 индекстегі мәнді азайттық.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.