Пребројте ги и вклучете ги пребарувањата на бинарна низа


Ниво на тешкотија Тешко
Често прашувано во Амазон Facebook Google Uber
Низа Сегментно дрво

An низа со големина n е дадена како влезна вредност. Проблемот „Пребројте ги и заменете ги пребарувањата на бинарна низа“ бара да извршите некои од пребарувањата дадени подолу, пребарувањата може да варираат на случаен начин.

Барањата се

Вклучи пребарување ⇒ вклучи (започнува, завршува), ова пребарувачко вклучување значи, смени 0 во 1 или 1 во 0 во рамките на дадениот опсег.

Број на барање ⇒ брои (почеток, крај), ова барање за броење значи да се брои целиот број на оние во дадениот опсег.

пример

n = 5
toggle(0, 1)
toggle(2, 3)
count(1, 2)
toggle(1, 4)
count(0, 2)
Count of all the ones within the range 1 and 2 is 2.
The count of all the ones within the range 0 and 2 is 1.

објаснување: Бројот на еден е отпечатен на секое барање за броење.

Пребројте ги и вклучете ги пребарувањата на бинарна низа

Алгоритам

  1. Проверете дали е Булово дрво е точно или неточно. Ако е точно, тогаш означете го тој јазол како неточен. Ажурирајте ја вредноста во сегмент дрво како крај - започнува + 1 сегмент Дрво [јазол].
  2. Проверете дали не е јазол на листот, а потоа поставете ја или превртете ја вредноста на дрво на деца.
  3. Ако вредностите се надвор од опсегот, тогаш вратете се.
  4. Проверете дали сегмент дрво дојдете во опсег, ако е точно, тогаш ажурирајте го вредниот тековен елемент на segmentTree како разлика и проверете повторно дали не е јазол на листот и направете ја истата постапка како во чекор 2.
  5. Проверете дали сегментот дрво не е во опсег и дали вредностите зафаќаат од двете страни на сегментот дрво, тогаш направете рекурзивен повик.
  6. Ажурирајте ја вредноста на тековниот јазол на јазолот segmentTree како резултат на нивните деца.

За барање за броење

  1. Проверете дали тековниот јазол е надвор од опсегот, а потоа вратете 0.
  2. Потоа, видете дали е точен тековниот јазол на boolTrees, ако е точно, тогаш означете го тековниот јазол на boolTrees за да не биде лажно и ажурирајте ја моменталната вредност на јазолот на segmentTree како разлика.
  3. Проверете дали не е лист јазол и превртете ги вредностите на децата.
  4. Проверете дали segmentTree лежи во дадениот опсег, а потоа вратете го segmentTree [јазолот].
  5. Ако не, тогаш рекурзивно ја повикувате функцијата за да не се преклопува.

Објаснување

Дадовме низа од n, така што сите нејзини вредности се иницијализираат на 0. toе извршиме со оглед на две пребарувања што се вклучуваат пребарување, што треба да ги преврти сите 0 во 1 и сите 1 во 0 во дадениот опсег . Барањето за броење е да се избројат сите нули присутни во дадениот опсег. Toе користиме segmentTree што е иницијализирано како 0. Значи, го претвораме во 1-и во рамките на опсегот.

Кога и да се повика функцијата за вклучување, ќе ја бараме Буловата низа што ја создадовме како boolTree, иницијализирана како неточна, ќе провериме дали вредноста на тековниот јазол на boolTree е точна или неточна, ако е погрешна, значи дека има некое од ажурирањата не е направено до сега. Значи, треба да го сториме тоа, и ако е точно, пред сè, го означуваме како лажен, за да можеме да го користиме подоцна и да ја ажурираме вредноста на сегментот дрво на тековниот јазол како збир на разликата на завршувањето и започнувањето и разликата од 1 и вредноста на тековниот јазол на сегментотTree. Beе провериме дали тоа не е лист јазол, бидејќи ако е, нема да правиме операции после тоа. Ако не е, тогаш ќе ги ажурираме вредностите на детскиот јазол како Булова вредност.

Проверете дали тековниот сегмент на segmentTree е во даден опсег или не. Ако не, тогаш остварете рекурзивни повици за сегментот на јазли да влезе во дадениот опсег.

Истата работа е да се направи со функцијата за броење, но со малку поинаков пристап. Е провериме дали тековниот јазол не треба да биде надвор од опсегот ако едноставно ја врати вредноста 0.

Проверете дали тековниот јазол не треба да биде обележан со тековниот јазол на segmentTree. Ако е точно, ажурирајте го тековниот јазол како неточен и ажурирајте ги вредностите на тековниот јазол на сегментот Дрво како збир од разликата на завршувањето и стартувањето и разликата од 1 и тековниот јазол на семенското дрво што го направивме во функцијата за вклучување, повторно проверете дали е не лист, а потоа одете напред со ажурирањето на детските јазли. Досега во овој момент, ние ги направивме сите предусловни методи за да го вратиме одговорот, за тоа ќе провериме дали тековниот сегмент на јазли лежи во дадениот опсег и ќе ја вратиме тековната вредност на јазолот segmentTree. Else рекурзивно ја повикува функцијата за да ја направи во рамките на опсегот.

Имплементација

C ++ код за броење и вклучување на пребарувања на бинарна низа

#include<iostream>
using namespace std;

const int MAX = 100000;

int segmentTree[MAX] = {0};

bool boolTree[MAX] = {false};

void toggle(int node, int starting, int ending, int rangeStart, int rangeEnding)
{
    if (boolTree[node])
    {
        boolTree[node] = false;
        segmentTree[node] = ending - starting + 1 - segmentTree[node];

        if (starting < ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[1+(node<<1)] = !boolTree[1+(node<<1)];
        }
    }
    if (starting>ending || rangeStart > ending || rangeEnding < starting)
        return ;
    if (rangeStart<=starting && ending<=rangeEnding)
    {
        segmentTree[node] = ending-starting+1 - segmentTree[node];
        if (starting < ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[1+(node<<1)] = !boolTree[1+(node<<1)];
        }
        return;
    }
    int mid = (starting+ending)/2;
    toggle((node<<1), starting, mid, rangeStart, rangeEnding);
    toggle((node<<1)+1, mid+1,ending, rangeStart, rangeEnding);
    if (starting < ending)
        segmentTree[node] = segmentTree[node<<1] + segmentTree[(node<<1)+1];
}

int count(int node, int starting, int ending, int qs, int qe)
{
    if (starting>ending || qs > ending || qe < starting)
        return 0;

    if (boolTree[node])
    {
        boolTree[node] = false;
        segmentTree[node] = ending-starting+1-segmentTree[node];

        if (starting<ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[(node<<1)+1] = !boolTree[(node<<1)+1];
        }
    }
    if (qs<=starting && ending<=qe)
        return segmentTree[node];

    int mid = (starting+ending)/2;
    return count((node<<1), starting, mid, qs, qe) +
           count((node<<1)+1, mid+1, ending, qs, qe);
}

int main()
{
    int n = 5;
    toggle(1, 0, n-1, 0, 1);
    toggle(1, 0, n-1, 2, 3);
    cout << count(1, 0, n-1, 1, 2) << endl;
    toggle(1, 0, n-1, 1, 4);
    cout << count(1, 0, n-1, 0, 2) << endl;

    return 0;
}
2
1

Java код за броење и вклучување на пребарувања на бинарна низа

class toggleAndCount
{
    static final int MAX = 100000;

    static int segmentTree[] = new int[MAX];

    static boolean boolTree[] = new boolean[MAX];

    static void toggle(int node, int starting,int ending, int rangeStart, int rangeEnding)
    {
        if (boolTree[node])
        {
            boolTree[node] = false;
            segmentTree[node] = ending - starting + 1 - segmentTree[node];

            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[1 + (node << 1)] = !boolTree[1 + (node << 1)];
            }
        }
        if (starting > ending || rangeStart > ending || rangeEnding < starting)
        {
            return;
        }
        if (rangeStart <= starting && ending <= rangeEnding)
        {
            segmentTree[node] = ending - starting + 1 - segmentTree[node];
            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[1 + (node << 1)] = !boolTree[1 + (node << 1)];
            }
            return;
        }

        int mid = (starting + ending) / 2;
        toggle((node << 1), starting, mid, rangeStart, rangeEnding);
        toggle((node << 1) + 1, mid + 1, ending, rangeStart, rangeEnding);
        if (starting < ending)
        {
            segmentTree[node] = segmentTree[node << 1] +segmentTree[(node << 1) + 1];
        }
    }
    static int count(int node, int starting,int ending, int qs, int qe)
    {
        if (starting > ending || qs > ending || qe < starting)
        {
            return 0;
        }
        if (boolTree[node])
        {
            boolTree[node] = false;
            segmentTree[node] = ending - starting + 1 - segmentTree[node];

            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[(node << 1) + 1] = !boolTree[(node << 1) + 1];
            }
        }
        if (qs <= starting && ending <= qe)
        {
            return segmentTree[node];
        }
        int mid = (starting + ending) / 2;
        return count((node << 1), starting, mid, qs, qe) + count((node << 1) + 1, mid + 1, ending, qs, qe);
    }
    public static void main(String args[])
    {
        int n = 5;

        toggle(1, 0, n-1, 0, 1);
        toggle(1, 0, n-1, 2, 3);
        System.out.println( count(1, 0, n-1, 1, 2));
        toggle(1, 0, n-1, 1, 4);
        System.out.println(count(1, 0, n-1, 0, 2));
    }
}

2
1

Анализа на сложеност за пребарување на броење и промена на бинарна низа

Временска комплексност

O (q * log n) каде "Q" е бројот на пребарувања и „Н“ е големината на низата.

Комплексноста на просторот

Тој) каде „Н“ е големината на низата.

Суд