Заявки за обхват на обхвата без актуализации


Ниво на трудност Лесно
Често задавани в BlackRock GE Healthcare Moonfrog Labs Synopsys Такси4 Разбира се Twilio
Array Ларсен и Тубро Задача за заявка

Декларация за проблема

Проблемът „Заявки за обхват на обхвата без актуализации“ гласи, че имате масив of числа и диапазон. Постановката на проблема изисква да се открие сумата на всички елементи в дадения диапазон.

Пример

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

Обяснение

Сумата от всички числа между диапазона (0, 4) включително е 40, а сумата от всички числа между диапазона (1, 3) включително е 24.

Заявки за обхват на обхвата без актуализации

 

алгоритъм

  1. Създайте масив sumArray с размер, същият като дадения масив.
  2. Преминете през дадения масив и съхранявайте сумата от предишния елемент на sumArray и текущия елемент на дадения масив и го съхранявайте в sumArray.
  3. За всяка заявка, ако лявото е равно на 0, връщайте sumArray [вдясно],
  4. В противен случай върнете sumArray [вдясно] - sumArray [вляво - 1].

Обяснение

Дадохме масив от цяло число и диапазон, поискахме да разберем сумата от всички елементи в дадения диапазон за всяка заявка. Всяка от заявките се състои от диапазон като начална и крайна точка на диапазон. Този въпрос не включва заявка за актуализация. Това означава, че няма нужда да актуализирате нито едно от нещата, докато откривате отговора на заявката. Ние просто ще изградим дадения масив, така че сумата от всички елементи от индекс 0 до текущ индекс да е в i-то място на изградения масив. По този начин всяка заявка ще бъде решена в O (1), с допълнително пространство O (n).

Ще изградим sumArray, който създадохме. В този sumArray сумата от елементи от 0 до i ще се съхранява на i-то място на sumArray. Ще изчислим това, тъй като ще съберем предишната стойност на sumArray и текущата стойност на дадения масив и ще го съхраним в текущата позиция на индекса на sumArray по време на обхождане. Така че, когато някой попита каква е сумата от всички числа на тази позиция, ние просто трябва да върнем стойността на тази позиция за всеки уникален елемент на масив.

Когато получим заявка, състояща се от произволен диапазон, и ако открием, че лявата или началната точка на диапазона е равна на 0, просто ще върнем стойността на sumArray [вдясно], това, което обсъдихме по-горе, е лявият диапазон е не е равно на 0 ще върнем разликата между sumArray [вдясно] и sumArray [вляво-1]. Това ще бъдат задължителни отговори. Този подход е и един от най-лесните начини, по които използваме Динамично програмиране.

код

C ++ код за заявки за обхват на обхвата без актуализации

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

Java код за запитвания за сума от обхват без актуализации

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

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

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

O (N + Q),  защото се нуждаем от O (N), за да изчислим sumArray и след това O (1) време за всяка заявка.

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

Тук в дадения подход създадохме нов масив sumArray за съхраняване на сумата от елементи от 0 до i. По този начин този подход изисква НА) пространство. Но можехме да модифицираме и оригиналния масив. Тогава космическата сложност би била намалена до постоянна.