Бројање и пребацивање упита на бинарном низу


Ниво тешкоће Тежак
Често питани у амазонка фацебоок гоогле Убер
Ред Сегментно дрво

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

Упити су ⇒

Укључи / искључи пребацивање упита (почетак, завршетак), ово пребацивање упита значи, променити 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.

objašnjenje: На сваком упиту за бројање исписује се број један.

Бројање и пребацивање упита на бинарном низу

Алгоритам

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

За упит бројања

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

Објашњење

Дали смо низ од н таквих да су све његове вредности иницијализоване на 0. Извршићемо задата два упита која укључују пребацивање упита, а то је да инвертирамо све 0 у 1 и све 1 у 0 у датом опсегу . Упит за бројање је да се преброје све нуле присутне у датом опсегу. Користићемо сегментТрее које је иницијализовано као 0. Дакле, претварамо га у 1с унутар опсега.

Кад год се позове функција пребацивања, тражићемо логички низ који смо креирали као боолТрее који је иницијализован као фалсе, проверићемо да ли је тренутна вредност чвора боолТрее тачна или нетачна, ако је лажна, значи да било која од исправки има није урађено до сада. Дакле, то морамо да урадимо, и ако је тачно, пре свега, означавамо га као нетачно, да бисмо га касније могли користити и ажурирати вредност сегментТрее на тренутном чвору као збир разлике завршетка и почетка и разлика од 1 и тренутне вредности чвора сегментТрее. Проверићемо да ли је чвор у облику листа, јер ако јесте, после тога нећемо извршити операције. Ако није, тада ћемо ажурирати вредности чвора подређених као логичке вредности.

Проверите да ли је тренутни сегмент сегментТрее унутар датог опсега или не. У супротном, упутите рекурзивне позиве тако да сегмент чворова уђе у задати опсег.

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

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

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

Ц ++ код за бројање и пребацивање упита на бинарном низу

#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

Јава код за бројање и пребацивање упита на бинарном низу

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

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

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

О (к * лог н) где "К" је број упита и „Н“ је величина низа.

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

Он) где „Н“ је величина низа.

Препорука