Подсчет и переключение запросов на двоичном массиве

// C ++ программа для реализации переключения и подсчета
// запросы к двоичному массиву.
#include<bits/stdc++.h>

using namespace std;

const int MAX = 100000;

  
// сегментируем дерево для хранения количества единиц в пределах диапазона

int tree[MAX] = {0};

  
// дерево типов bool для сбора обновлений для переключения
// значения 1 и 0 в заданном диапазоне

bool lazy[MAX] = {false};

  
// функция сбора обновлений переключения
// узел -> индекс текущего узла в дереве сегментов
// st -> начальный индекс текущего узла
// en -> конечный индекс текущего узла
// us -> начальный индекс запроса на обновление диапазона
// ue -> конечный индекс запроса на обновление диапазона

void toggle(int node, int st, int en, int us, int ue)

{

    // Если ленивое значение ненулевое для текущего узла сегмента

    // дерево, то есть ожидающие обновления. Итак, нам нужно

    // чтобы убедиться, что ожидающие обновления сделаны раньше

    // делаем новые обновления. Поскольку это значение может быть использовано

    // родитель после рекурсивных вызовов (см. последнюю строку этого

    // функция)

    if (lazy[node])

    {

        // Производим ожидающие обновления, используя значения, хранящиеся в ленивых узлах

        lazy[node] = false;

        tree[node] = en - st + 1 - tree[node];

        // проверка, не является ли это листовым узлом, потому что если

        // это листовой узел, тогда мы не можем идти дальше

        if (st < en)

        {

            // Мы можем отложить обновление детей, которых мы не делаем

            // нужны их новые значения сейчас.

            // Поскольку мы еще не обновляем дочерние элементы узла,

            // нам нужно установить ленивые флаги для детей

            lazy[node<<1] = !lazy[node<<1];

            lazy[1+(node<<1)] = !lazy[1+(node<<1)];

        }

    }

    // вне зоны доступа

    if (st>en || us > en || ue < st)

        return ;

    // Текущий сегмент полностью в диапазоне

    if (us<=st && en<=ue)

    {

        // Добавить разницу к текущему узлу

        tree[node] = en-st+1 - tree[node];

        // та же логика для проверки конечного узла или нет

        if (st < en)

        {

            // Здесь мы храним значения в ленивых узлах,

            // вместо обновления самого дерева сегментов

            // Поскольку нам не нужны эти обновленные значения сейчас

            // мы откладываем обновления, сохраняя значения в lazy []

            lazy[node<<1] = !lazy[node<<1];

            lazy[1+(node<<1)] = !lazy[1+(node<<1)];

        }

        return;

    }

    // Если не полностью в звене, но перекрывается, повторить для

    // дети,

    int mid = (st+en)/2;

    toggle((node<<1), st, mid, us, ue);

    toggle((node<<1)+1, mid+1,en, us, ue);

    // И использовать результат дочерних вызовов для обновления этого узла

    if (st < en)

        tree[node] = tree[node<<1] + tree[(node<<1)+1];

}

  
/ * узел -> Индекс текущего узла в дереве сегментов.

          Первоначально 0 передается, поскольку root всегда находится в '

          индекс 0

   st & en -> Начальный и конечный индексы

                сегмент, представленный текущим узлом,

                то есть дерево [узел]

   qs & qe -> начальные и конечные индексы запроса

                ассортимент */

// функция для подсчета количества единиц в заданном диапазоне

int countQuery(int node, int st, int en, int qs, int qe)

{

    // текущий узел находится вне диапазона

    if (st>en || qs > en || qe < st)

        return 0;

    // Если для текущего узла дерева сегментов установлен ленивый флаг,

    // тогда есть некоторые ожидающие обновления. Итак, нам нужно

    // убедитесь, что ожидающие обновления сделаны до

    // обработка запроса к сумме

    if (lazy[node])

    {

        // Сделать ожидающие обновления для этого узла. Обратите внимание, что это

        // узел представляет сумму элементов в arr [st..en] и

        // все эти элементы должны быть увеличены на lazy [node]

        lazy[node] = false;

        tree[node] = en-st+1-tree[node];

        // проверка, не является ли это листовым узлом, потому что если

        // это листовой узел, тогда мы не можем идти дальше

        if (st<en)

        {

            // Так как мы еще не обновляем детей os si,

            // нам нужно установить ленивые значения для детей

            lazy[node<<1] = !lazy[node<<1];

            lazy[(node<<1)+1] = !lazy[(node<<1)+1];

        }

    }

    // На данный момент мы уверены, что отложенные обновления отложены

    // сделано для текущего узла. Таким образом, мы можем вернуть значение

    // Если этот сегмент лежит в диапазоне

    if (qs<=st && en<=qe)

        return tree[node];

    // Если часть этого сегмента перекрывается с заданным диапазоном

    int mid = (st+en)/2;

    return countQuery((node<<1), st, mid, qs, qe) +

           countQuery((node<<1)+1, mid+1, en, qs, qe);

}

  
// Драйвер программы для запуска дела

int main()

{

    int n = 5;

    toggle(1, 0, n-1, 1, 2);  // Переключить 1 2

    toggle(1, 0, n-1, 2, 4);  // Toggle 2 4

    cout << countQuery(1, 0, n-1, 2, 3) << endl;  // Счет 2 3

    toggle(1, 0, n-1, 2, 4);  // Toggle 2 4

    cout << countQuery(1, 0, n-1, 1, 4) << endl;  // Счет 1 4

   return 0;

}

// Java-программа для реализации переключения и
// считать запросы в двоичном массиве.

class GFG

{

static final int MAX = 100000;

  
// сегментное дерево для хранения количества
// из 1 в пределах диапазона

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

  
// дерево типов bool для сбора обновлений
// для переключения значений 1 и 0 в
// заданный диапазон

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

  
// функция сбора обновлений переключения
// узел -> индекс текущего узла в дереве сегментов
// st -> начальный индекс текущего узла
// en -> конечный индекс текущего узла
// us -> начальный индекс запроса на обновление диапазона
// ue -> конечный индекс запроса на обновление диапазона

static void toggle(int node, int st, 

                   int en, int us, int ue) 

{

    // Если ленивое значение ненулевое для текущего

    // узел дерева сегментов, то есть

    // некоторые ожидающие обновления. Итак, нам нужно

    // чтобы убедиться, что ожидающие обновления

    // сделано перед выполнением новых обновлений.

    // Потому что это значение может быть использовано

    // родитель после рекурсивных вызовов (см. последний

    // строка этой функции)

    if (lazy[node])

    {

        // Сделать ожидающие обновления, используя значение

        // хранится в ленивых узлах

        lazy[node] = false;

        tree[node] = en - st + 1 - tree[node];

        // проверка, не является ли это листовым узлом

        // потому что если это листовой узел, то

        // мы не можем идти дальше

        if (st < en)

        {

            // Мы можем отложить обновление детей

            // нам сейчас не нужны их новые значения.

            // Так как мы еще не обновляем детей

            // узла, нам нужно установить ленивые флаги

            // для детей

            lazy[node << 1] = !lazy[node << 1];

            lazy[1 + (node << 1)] = !lazy[1 + (node << 1)];

        }

    }

    // вне зоны доступа

    if (st > en || us > en || ue < st) 

    {

        return;

    }

    // Текущий сегмент полностью в диапазоне

    if (us <= st && en <= ue)

    {

        // Добавить разницу к текущему узлу

        tree[node] = en - st + 1 - tree[node];

        // та же логика для проверки конечного узла или нет

        if (st < en)

        {

            // Здесь мы храним значения в ленивых узлах,

            // вместо обновления самого дерева сегментов

            // Поскольку нам не нужны эти обновленные значения сейчас

            // мы откладываем обновления, сохраняя значения в lazy []

            lazy[node << 1] = !lazy[node << 1];

            lazy[1 + (node << 1)] = !lazy[1 + (node << 1)];

        }

        return;

    }

    // Если не полностью в звании,

    // но перекрываются, повторяются для детей,

    int mid = (st + en) / 2;

    toggle((node << 1), st, mid, us, ue);

    toggle((node << 1) + 1, mid + 1, en, us, ue);

    // И использовать результат детей

    // вызывает обновить этот узел

    if (st < en) 

    {

        tree[node] = tree[node << 1] +

                     tree[(node << 1) + 1];

    }

}

  
/ * узел -> Индекс текущего узла в дереве сегментов.

    Первоначально 0 передается, поскольку root всегда находится в '

    индекс 0

st & en -> Начальный и конечный индексы

            сегмент, представленный текущим узлом,

            то есть дерево [узел]

qs & qe -> начальные и конечные индексы запроса

            ассортимент */

// функция для подсчета количества единиц
// в заданном диапазоне

static int countQuery(int node, int st, 

                      int en, int qs, int qe)

{

    // текущий узел находится вне диапазона

    if (st > en || qs > en || qe < st)

    {

        return 0;

    }

    // Если для текущего установлен ленивый флаг

    // узел дерева сегментов, то есть

    // ожидающие обновления Итак, мы

    // нужно убедиться, что ожидающий

    // обновления выполняются перед обработкой

    // запрос к сумме

    if (lazy[node])

    {

        // Сделать ожидающие обновления для этого узла.

        // Обратите внимание, что этот узел представляет сумму

        // элементов в arr [st..en] и

        // все эти элементы должны быть увеличены

        // ленивый [узел]

        lazy[node] = false;

        tree[node] = en - st + 1 - tree[node];

        // проверка, не является ли это листовым узлом, потому что если

        // это листовой узел, тогда мы не можем идти дальше

        if (st < en) 

        {

            // Так как мы еще не обновляем детей os si,

            // нам нужно установить ленивые значения для детей

            lazy[node << 1] = !lazy[node << 1];

            lazy[(node << 1) + 1] = !lazy[(node << 1) + 1];

        }

    }

    // На данный момент мы уверены, что в ожидании

    // ленивые обновления сделаны для текущего узла.

    // Так что мы можем вернуть значение, если этот сегмент

    // лежит в диапазоне

    if (qs <= st && en <= qe)

    {

        return tree[node];

    }

    // Если часть этого сегмента перекрывается

    // с заданным диапазоном

    int mid = (st + en) / 2;

    return countQuery((node << 1), st, mid, qs, qe) + 

           countQuery((node << 1) + 1, mid + 1, en, qs, qe);

}

  
// Код драйвера

public static void main(String args[])

{

    int n = 5;

    toggle(1, 0, n - 1, 1, 2); // Переключить 1 2

    toggle(1, 0, n - 1, 2, 4); // Toggle 2 4

    System.out.println(countQuery(1, 0, n - 1, 2, 3)); // Счет 2 3

    toggle(1, 0, n - 1, 2, 4); // Toggle 2 4

    System.out.println(countQuery(1, 0, n - 1, 1, 4)); // Счет 1 4

}
}

  
// Этот код предоставлен 29AjayKumar

// C # программа для реализации переключения и
// считать запросы в двоичном массиве.

using System;

public class GFG{

    static readonly int MAX = 100000; 

    // сегментное дерево для хранения количества

    // из 1 в пределах диапазона

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

    // дерево типов bool для сбора обновлений

    // для переключения значений 1 и 0 в

    // заданный диапазон

    static bool []lazy = new bool[MAX]; 

    // функция сбора обновлений переключения

    // узел -> индекс текущего узла в дереве сегментов

    // st -> начальный индекс текущего узла

    // en -> конечный индекс текущего узла

    // us -> начальный индекс запроса на обновление диапазона

    // ue -> конечный индекс запроса на обновление диапазона

    static void toggle(int node, int st, 

                    int en, int us, int ue) 

    { 

        // Если ленивое значение ненулевое для текущего

        // узел дерева сегментов, то есть

        // некоторые ожидающие обновления. Итак, нам нужно

        // чтобы убедиться, что ожидающие обновления

        // сделано перед выполнением новых обновлений.

        // Потому что это значение может быть использовано

        // родитель после рекурсивных вызовов (см. последний

        // строка этой функции)

        if (lazy[node]) 

        { 

            // Сделать ожидающие обновления, используя значение

            // хранится в ленивых узлах

            lazy[node] = false; 

            tree[node] = en - st + 1 - tree[node]; 

            // проверка, не является ли это листовым узлом

            // потому что если это листовой узел, то

            // мы не можем идти дальше

            if (st < en) 

            { 

                // Мы можем отложить обновление детей

                // нам сейчас не нужны их новые значения.

                // Так как мы еще не обновляем детей

                // узла, нам нужно установить ленивые флаги

                // для детей

                lazy[node << 1] = !lazy[node << 1]; 

                lazy[1 + (node << 1)] = !lazy[1 + (node << 1)]; 

            } 

        } 

        // вне зоны доступа

        if (st > en || us > en || ue < st) 

        { 

            return; 

        } 

        // Текущий сегмент полностью в диапазоне

        if (us <= st && en <= ue) 

        { 

            // Добавить разницу к текущему узлу

            tree[node] = en - st + 1 - tree[node]; 

            // та же логика для проверки конечного узла или нет

            if (st < en) 

            { 

                // Здесь мы храним значения в ленивых узлах,

                // вместо обновления самого дерева сегментов

                // Поскольку нам не нужны эти обновленные значения сейчас

                // мы откладываем обновления, сохраняя значения в lazy []

                lazy[node << 1] = !lazy[node << 1]; 

                lazy[1 + (node << 1)] = !lazy[1 + (node << 1)]; 

            } 

            return; 

        } 

        // Если не полностью в звании,

        // но перекрываются, повторяются для детей,

        int mid = (st + en) / 2; 

        toggle((node << 1), st, mid, us, ue); 

        toggle((node << 1) + 1, mid + 1, en, us, ue); 

        // И использовать результат детей

        // вызывает обновить этот узел

        if (st < en) 

        { 

            tree[node] = tree[node << 1] + 

                        tree[(node << 1) + 1]; 

        } 

    } 

    / * узел -> Индекс текущего узла в дереве сегментов.

        Первоначально 0 передается, поскольку root всегда находится в '

        индекс 0

    st & en -> Начальный и конечный индексы

                сегмент, представленный текущим узлом,

                то есть дерево [узел]

    qs & qe -> начальные и конечные индексы запроса

                ассортимент */

    // функция для подсчета количества единиц

    // в заданном диапазоне

    static int countQuery(int node, int st, 

                        int en, int qs, int qe) 

    { 

        // текущий узел находится вне диапазона

        if (st > en || qs > en || qe < st) 

        { 

            return 0; 

        } 

        // Если для текущего установлен ленивый флаг

        // узел дерева сегментов, то есть

        // ожидающие обновления Итак, мы

        // нужно убедиться, что ожидающий

        // обновления выполняются перед обработкой

        // запрос к сумме

        if (lazy[node]) 

        { 

            // Сделать ожидающие обновления для этого узла.

            // Обратите внимание, что этот узел представляет сумму

            // элементов в arr [st..en] и

            // все эти элементы должны быть увеличены

            // ленивый [узел]

            lazy[node] = false; 

            tree[node] = en - st + 1 - tree[node]; 

            // проверка, не является ли это листовым узлом, потому что если

            // это листовой узел, тогда мы не можем идти дальше

            if (st < en) 

            { 

                // Так как мы еще не обновляем детей os si,

                // нам нужно установить ленивые значения для детей

                lazy[node << 1] = !lazy[node << 1]; 

                lazy[(node << 1) + 1] = !lazy[(node << 1) + 1]; 

            } 

        } 

        // На данный момент мы уверены, что в ожидании

        // ленивые обновления сделаны для текущего узла.

        // Так что мы можем вернуть значение, если этот сегмент

        // лежит в диапазоне

        if (qs <= st && en <= qe) 

        { 

            return tree[node]; 

        } 

        // Если часть этого сегмента перекрывается

        // с заданным диапазоном

        int mid = (st + en) / 2; 

        return countQuery((node << 1), st, mid, qs, qe) + 

            countQuery((node << 1) + 1, mid + 1, en, qs, qe); 

    } 

    // Код драйвера

    public static void Main() 

    { 

        int n = 5; 

        toggle(1, 0, n - 1, 1, 2); // Переключить 1 2

        toggle(1, 0, n - 1, 2, 4); // Toggle 2 4

        Console.WriteLine(countQuery(1, 0, n - 1, 2, 3)); // Счет 2 3

        toggle(1, 0, n - 1, 2, 4); // Toggle 2 4

        Console.WriteLine(countQuery(1, 0, n - 1, 1, 4)); // Счет 1 4

    } 

} 

  
/ * Этот код предоставлен PrinciRaj1992 * /