Массивдеги туруктуу убакыт аралыгы


Кыйынчылык деңгээли жеңил
Көп суралган CodeNation DE Shaw Directi Expedia Гугл
согуштук тизме Динамикалык программалоо

Сиз ан бердиңиз бүтүн согуштук тизме жана башында, ал 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}

Массивдеги туруктуу убакыт аралыгы

 

Algorithm

  1. Ар бир суроо боюнча кадамдарды аткарыңыз.
    1. Массивдин сол индексине берилген маанини кошуп, өзүнө сактаңыз.
    2. Укук мааниси массивдин акыркы индексине барабар эместигин текшериңиз, андан кийин массивдин оң + 1 позициясында берилген маанини алып салып, өзүнө сактаңыз.
  2. Массивди басып чыгаруудан мурун массивди массивдин арасынан өтүү жолу менен жаңыртып, мурунку жана учурдагы маанисин кошуп, массивдин өзүнө сактаңыз.
  3. Жаңыртуудан кийин, алынган массивди басып чыгарыңыз.

Массивде туруктуу убакыт аралыгын кошуу боюнча түшүндүрмө

Бүтүн массив жана кошула турган сан берилген. Бизге дагы бир катар суроолор берилген. Анда диапазондун баштапкы чекити сол жагында, ал эми аяктоочу чекити оң жагында камтылган. Берилген диапазондогу берилген санды мүмкүн болгон бүтүн сандарга кошуу сунушталды. Андан кийин, натыйжада, массивди басып чыгарыңыз. Бул үчүн, биз кошуу операциясын абдан модификацияланган жол менен аткарганы жатабыз. Массив индексинин маанилерин массивдин сол жана оң жагында + 1 позициясында берилген маани менен толтурабыз жана ал массивди жаңыртуудан мурун.

Ар бир берилген суроого, солго жана оңго, берилген мааниде оң жактагы сол индекске кошобуз, сол индексте гана эсиңизде болсун. Ал эми туура маани үчүн, маани укугу массивдин акыркы индексине барабар эместигин текшеребиз, эгерде берилген шарт канааттандырылса, анда берилген маани индексин жаңырта турган болсок, берилген маанини чыгарабыз массивдин оң индекси жана аны массивдин өзү туура позиция индексинде сактоо. Ар бир суроо боюнча биз ушул операцияларды жасайбыз.

Эми биз массивди басып чыгарышыбыз керек, бирок ага чейин биз бардык баалуулуктарды жаңыртканы жатабыз, биз кошкон операция, биз аны жаңыртышыбыз керек. Ошентип, массивди аралап өтүп, берилген массивдин учурдагы жана мурунку маанисин кошуп, массивди жаңыртып, аны массивдин учурдагы абалына сактаңыз. Андан кийин, биз массивди басып чыгарганы жатабыз.

коду

Массивде туруктуу убакыт аралыгын кошуу үчүн С ++ тилинде ишке ашыруу

#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" массивдеги элементтердин саны.