Сураныч, жаңыртуулар жок сумма


Кыйынчылык деңгээли жеңил
Көп суралган Кара таш GE Саламаттыкты сактоо Moonfrog Labs Synopsys Taxi4Sure Twilio
согуштук тизме Ларсен & Toubro Query Problem

Маселени билдирүү

"Жаңылануусуз сумма сурамдары" көйгөйүндө сизде ан согуштук тизме of бүтүн жана диапазону. Маселенин коюлушу берилген аралыктагы бардык элементтердин суммасын табууну сурайт.

мисал

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

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

түшүндүрүү

(0, 4) диапазонунун ортосундагы бардык сандардын суммасы 40ка, ал эми (1, 3) диапазонундагы бардык сандардын суммасы 24кө барабар.

Сураныч, жаңыртуулар жок сумма

 

Algorithm

  1. Берилген массив менен бирдей көлөмдөгү сумма массивин түзүү.
  2. Берилген массив аркылуу өтүп, sumArray мурунку элементинин жана берилген массивдин учурдагы элементинин суммасын сактап, sumArray ичине сактаңыз.
  3. Ар бир суроо үчүн, эгер сол 0го барабар болсо, анда sumArray [оңго],
  4. Башкасы sumArray [оң] - sumArray [сол - 1] кайтарып берет.

түшүндүрүү

Биз бүтүндөй бир массивди жана диапазонду бердик, ар бир суроо боюнча берилген диапазондогу бардык элементтердин суммасын билүү сунушталды. Суроолордун ар бири диапазондун башталышы жана аяктоочу чекити катарында диапазондон турат. Бул суроого эч кандай жаңыртуу суроосу кирбейт. Демек, суроонун жообун таап жатып, бир дагы нерсени жаңыртуунун кажети жок. Берилген массивди 0 индексинен учурдагы индекске чейинки бардык элементтердин суммасы курулган массивдин ith позициясында тургандай кылып курабыз. Ушундайча, ар бир суроо O (n) ашыкча боштук менен O (1) чечилет.

Биз өзүбүз жараткан sumArray курабыз. Бул sumArrayде, 0дөн iге чейинки элементтердин суммасы sumArrayдин ith абалында сакталат. Биз муну эсептейбиз, анткени sumArrayдин мурунку маанисин жана берилген массивдин учурдагы маанисин кошуп, sumArrayдин учурдагы индекси абалына өтүүдө сактайбыз. Ошентип, кимдир бирөө ушул позициядагы бардык сандардын суммасы канча деп сураганда, биз ар бир уникалдуу массив элементтери үчүн ошол позициянын маанисин кайтарып беришибиз керек.

Каалаган диапазондон турган суроо-талапты алганда, эгер диапазондун сол же баштапкы чекити 0го барабар деп тапсак, анда биз сумманын маанисин кайтарып беребиз [оң], жогоруда биз талкууладык, сол диапазон 0ге барабар эмес, биз sumArray [оң] жана sumArray [сол-1] айырмасын кайтарабыз. Булар жоопторду талап кылат. Бул ыкма биз колдонгон эң жөнөкөй жолдордун бири Динамикалык программалоо.

коду

C ++ Code for Range суммасы боюнча суроолор жаңыртылбастан

#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),  sumArray эсептөө үчүн O (N) керек, андан кийин ар бир суроо үчүн O (1) убакыт керек.

Космостун татаалдыгы

Берилген ыкмада, элементтердин суммасын 0дон iге чейин сактоо үчүн жаңы sumArray массивин түздүк. Ошентип, бул ыкма талап кылат O (N) мейкиндик. Бирок биз баштапкы массивди дагы өзгөртө алмакпыз. Ошондо космостогу татаалдык туруктуу деңгээлге түшмөк.