Падлік і пераключэнне запытаў у двайковым масіве


Узровень складанасці Жорсткі
Часта пытаюцца ў амазонка 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. Праверце, ці правільна boolTree праўда ці ілжыва. Калі гэта праўда, адзначце гэты вузел як ілжывы. Абнавіце значэнне ў сегментДрэва як заканчэнне - пачатак + 1 сегментДрэва [вузел].
  2. Праверце, ці не гэта лісцевы вузел, а затым усталюйце або інвертуйце значэнне boolTree дзяцей.
  3. Калі значэнні выходзяць за межы дыяпазону, вяртайце.
  4. Праверце, калі сегментДрэва прыйсці ў дыяпазон, калі ісціна, то абнавіце бягучы элемент значэння segmentTree як розніцу і яшчэ раз праверце, ці не з'яўляецца ён вузлом ліста, і зрабіце тую ж працэдуру, што і на этапе 2.
  5. Праверце, ці не знаходзіцца сегментTree у дыяпазоне, і значэнні прыціскаюцца па абодва бакі сегментаTree, а затым зрабіце рэкурсіўны выклік.
  6. Абнавіце значэнне бягучага вузла вузла segmentTree па выніках іх дзяцей.

Для запыту падліку

  1. Праверце, ці знаходзіцца бягучы вузел па-за дыяпазонам, а потым вярніце 0.
  2. Тады паглядзіце, ці сапраўдны бягучы вузел boolTrees, калі праўдзівы, адзначце бягучы вузел boolTrees як ілжывы і абнавіце бягучае значэнне вузла segmentTree як розніцу.
  3. Праверце, ці не з'яўляецца гэта лісцем, і інвертуйце значэнні дзяцей.
  4. Праверце, ці знаходзіцца segmentTree у зададзеным дыяпазоне, а затым вярніце segmentTree [вузел].
  5. Калі не, то рэкурсіўна выклічце функцыю, каб яна не перакрывалася.

Тлумачэнне

Мы далі масіў з n такіх, каб усе яго значэнні былі ініцыялізаваны 0. Мы збіраемся выканаць дадзеныя два запыты, якія пераключаюць запыт, які заключаецца ў інвертаванні ўсіх 0 у 1 і ўсіх 1 у 0 у зададзеным дыяпазоне. . Запыт падліку заключаецца ў падліку ўсіх нулёў у дадзеным дыяпазоне. Мы будзем выкарыстоўваць segmentTree, якое ініцыялізавана як 0. Такім чынам, мы пераўтвараем яго ў 1s у дыяпазоне.

Кожны раз, калі выклікаецца функцыя пераключэння, мы будзем шукаць булевы масіў, які мы стварылі як boolTree, які быў ініцыялізаваны як ілжывы, мы праверым, ці сапраўднае значэнне вузла boolTree з'яўляецца сапраўдным ці ілжывым, калі яно ілжывае, азначае, што якое-небудзь з абнаўленняў мае не рабілася да гэтага часу. Такім чынам, нам трэба зрабіць гэта, і, калі гэта праўда, перш за ўсё, мы пазначаем гэта як ілжывае, таму мы можам выкарыстоўваць яго пазней і абнавіць значэнне segmentTree у бягучым вузле як суму розніцы ў канцоўцы і пачатку і розніца 1 і значэнне бягучага вузла segmentTree. Мы будзем правяраць, ці не з'яўляецца гэта лісцевым вузлом, таму што калі ён ёсць, мы не будзем рабіць аперацыі пасля гэтага. Калі гэта не так, мы абнавім значэнні даччынага вузла як лагічныя значэнні.

Праверце, ці знаходзіцца бягучы сегмент segmentTree у зададзеным дыяпазоне ці не. Калі няма, то рабіце рэкурсіўныя выклікі, каб сегмент вузлоў знаходзіўся ў зададзеным дыяпазоне.

Тое ж самае звязана з функцыяй падліку, але з некалькі іншым падыходам. Мы правяраем, што бягучы вузел не павінен выходзіць за межы дыяпазону, калі потым проста вяртае значэнне 0.

Праверце, калі бягучы вузел не пазначаны бягучым вузлом segmentTree. Калі true, абнавіце бягучы вузел як ілжывы і абнавіце значэнні бягучага вузла segmentTree як суму розніцы канца і старту і розніцы 1 і бягучага вузла segementTree, якую мы зрабілі пры пераключэнні функцыі, яшчэ раз праверым, ці ёсць гэта не лісток, а затым рухацца наперад з абнаўленнем дзяцей вузлоў. На дадзены момант мы зрабілі ўсе неабходныя метады, каб вярнуць адказ, для гэтага мы збіраемся праверыць, ці знаходзіцца бягучы сегмент вузлоў у зададзеным дыяпазоне, і вярнуць бягучае значэнне вузла segementTree. 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 * часопіс n) дзе "Q" - колькасць запытаў і "П" - памер масіва.

Касмічная складанасць

Аб (п) дзе "П" - памер масіва.

Спасылка