Диапазони доимии амалиёт дар массив илова мекунад  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад CodeNation DE Шо Directi Expedia Google
тартиботи ҳарбӣ Барномарезии динамикӣ

Шумо як додед ҳамаҷониба асал ва дар аввал, он ҳамчун 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 массив ва пеш аз чопи навсозии ин массив пур мекунем.

ҳамчунин нигаред
Массив фарқият | Дархости навсозии диапазон дар O (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 коҳиш додем, агар он дар ҳудуди массив бошад.

ҳамчунин нигаред
Гузоштани ҳадди аққал барои ташаккули палиндром бо ҷойивазкунии иҷозатдодашуда

Мураккабии фазо

О (Н) ки дар "N" шумораи унсурҳои массив аст.