Брой и превключване на заявки в двоичен масив  


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

An масив с размер n е дадена като входна стойност. Проблемът „Преброяване и превключване на заявки в двоичен масив“ изисква да се изпълнят някои от заявките, които са дадени по-долу, заявките могат да се различават произволно.

Запитванията са ⇒

Превключване на заявката ⇒ превключване (начало, край), това превключване на заявка означава, промяна на 0s на 1 или 1s на 0s в рамките на дадения диапазон.

Заявка за броене ⇒ брой (начална, завършваща), тази заявка за броене означава да се преброи целият брой на тези в дадения диапазон.

Пример  

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. Проверете дали Boolean boolTree е вярно или невярно. Ако е вярно, маркирайте този възел като фалшив. Актуализирайте стойността в segmentTree като край - начало + 1 сегментДърво [възел].
  2. Проверете дали това не е листен възел, след това задайте или обърнете стойността на boolTree деца.
  3. Ако стойностите са извън обхвата, върнете.
  4. Проверете дали segmentTree влезте в диапазон, ако е вярно, след това актуализирайте текущия елемент на стойност на segmentTree като разлика и проверете отново дали не е възел на листа и направете същата процедура, както в стъпка 2.
  5. Проверете дали segmentTree не е в обхват и стойностите се припокриват от двете страни на segmentTree, след което направете рекурсивно повикване.
  6. Актуализирайте стойността на текущия възел на възел segmentTree като резултат от техните деца.
Вижте също
Решаване на судоку

За заявка за броене

  1. Проверете дали текущият възел е извън обхвата, след което върнете 0.
  2. След това вижте дали текущият възел на boolTrees е true, ако е true, след това маркирайте текущия възел на boolTrees на false и актуализирайте текущата стойност на възела на segmentTree като разлика.
  3. Проверете дали това не е листен възел и обърнете стойностите на децата.
  4. Проверете дали segmentTree се намира в дадения диапазон, след което върнете segmentTree [възел].
  5. Ако не, тогава рекурсивно извикайте функцията, за да не се припокрива.

Обяснение  

Дадохме масив от n, така че всички негови стойности да бъдат инициализирани на 0. Ще изпълним дадени две заявки, които са с превключваща заявка, която трябва да обърне всички 0 в 1s и всички 1s в 0s в дадения диапазон . Заявката за преброяване е да преброи всички налични нули в дадения диапазон. Ще използваме segmentTree, което е инициализирано като 0. Така че го преобразуваме в 1s в диапазона.

Всеки път, когато се извика функцията за превключване, ще търсим булевия масив, който създадохме като boolTree, който беше инициализиран като false, ще проверим дали текущата стойност на възела на boolTree е вярна или невярна, ако е false означава, че някоя от актуализациите има не е правено до сега. Така че трябва да го направим и ако е вярно, на първо място, ние го маркираме като фалшиво, за да можем да го използваме по-късно и да актуализираме стойността на segmentTree в текущия възел като сума от разликата в края и началото и разликата в 1 и стойността на текущия възел на segmentTree. Ще проверяваме дали не е листен възел, защото ако е, няма да правим операции след това. Ако не е, тогава ще актуализираме стойностите на дъщерния възел като булеви стойности.

Вижте също
Намерете най-малката положителна целочислена стойност, която не може да бъде представена като сума от което и да е подмножество на даден масив

  

Проверете дали текущият сегмент на segmentTree е в даден диапазон или не. Ако не, тогава направете рекурсивни повиквания за такива, че сегментът на възлите да е в рамките на дадения диапазон.

Същото нещо е свързано с функцията за броене, но с малко по-различен подход. Ще проверим дали текущият възел не трябва да е извън обхвата, ако след това просто връща стойността 0.

Проверете дали текущият възел не трябва да бъде маркиран с текущия възел на segmentTree. Ако е вярно, актуализирайте текущия възел като false и актуализирайте стойностите на текущия възел на segmentTree като сумата от разликата в края и старта и разликата от 1 и текущия възел на segmentTree, което сме направили при превключване на функцията, отново проверяваме дали е не лист, след това се придвижете напред с актуализирането на децата възли. Досега на този етап направихме всички необходими методи, за да върнем отговора, за това ще проверим дали текущият сегмент от възли се намира в дадения диапазон и ще върнем текущата стойност на възела 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 * log n) където "Q" е броят на заявките и "н" е размерът на масива.

Вижте също
Отпечатайте десен изглед на двоично дърво

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

О (п) където "н" е размерът на масива.

препратка