Consultas de rango para contar el número de valores de paridad pares con actualizaciones

Dada una array arr[] de N enteros, la tarea es realizar las siguientes dos consultas: 

• consulta (L, R) : Imprime el número de números de paridad par en el subarreglo de L a R.
• update(i, x) : actualiza la referencia del elemento de array por índice i a x.

Ejemplos:  

Entrada: arr[] = {18, 15, 8, 9, 14, 5} 
Consulta 1: consulta (L = 0, R = 4) 
Consulta 2: actualización (i = 3, x = 11) 
Consulta 3: consulta ( L = 0, R = 4) 
Salida: 
3 
2 
Explicación:  
Consulta 1: El subarreglo es {18, 15, 8, 9, 14} 
Representación binaria de estos elementos – 
18 => 10010, Paridad = 2 
15 => 1111, Paridad = 4 
8 => 1000, Paridad = 1 
9 => 1001, Paridad = 2 
14 => 1110, Paridad = 3 
Subarreglo[0-4] tiene 3 elementos con paridad par. 
Consulta 2: Actualizar arr[3] = 11 
Array actualizada, {18, 15, 8, 11, 14, 5} 
Consulta 3: Subarreglo es {18, 15, 8, 11, 14} 
Representación binaria de estos elementos – 
18 => 10010, Paridad = 2 
15 => 1111, Paridad = 4 
8 => 1000, Paridad = 1 
11 => 1011, Paridad = 3 
14 => 1110, Paridad = 3 
Subarreglo[0- 4] tienen 2 elementos con paridad par. 
 

Enfoque: la idea es utilizar el árbol de segmentos para consultar el recuento de los elementos de paridad par en un rango de array y actualizarlos simultáneamente.
Podemos encontrar la paridad para el valor actual iterando a través de cada bit de la representación binaria del número y contando el número de bits establecidos. Luego verifique si la paridad es par o no. Si tiene paridad par, configúrelo en 1, de lo contrario, en 0.

Construyendo el árbol de segmentos:  

• Los Nodes hoja del árbol de segmentos se representan como 0 (si es un número de paridad impar) o 1 (si es un número de paridad par).
• Los Nodes internos del árbol de segmentos son iguales a la suma de sus Nodes secundarios, por lo tanto, un Node representa los números totales de paridad par en el rango de L a R con el rango [L, R] debajo de este Node y el subárbol debajo de él .

Manejo de consultas:  

• Consulta (L, R): cada vez que recibimos una consulta de principio a fin, podemos consultar el árbol de segmentos para la suma de Nodes en el rango de principio a fin, que a su vez representa el número de números de paridad par en el inicio del rango para terminar.
• Actualizar (i, x): para realizar una consulta de actualización para actualizar el valor en el índice i a x, verificamos los siguientes casos: 
  • Caso 1: si el valor anterior y el nuevo valor son números 
    de paridad par La cantidad de números de paridad par en el subarreglo no cambia, por lo que solo actualizamos el arreglo y no modificamos el árbol de segmentos
  • Caso 2: si el valor anterior y el nuevo valor no son números 
    de paridad par La cantidad de números de paridad par en el subarreglo no cambia, por lo que solo actualizamos el arreglo y no modificamos el árbol de segmentos
  • Caso 3: si el valor anterior es un número de paridad par pero el valor nuevo no es un número  de paridad par, el
    recuento de números de paridad par en el subarreglo disminuye, por lo que actualizamos el arreglo y agregamos -1 a cada rango. El índice i que se va a actualizar forma parte del árbol de segmentos.
  • Caso 4: si el valor anterior no es un número de paridad par pero el valor nuevo es un número  de paridad par, el
    recuento de números de paridad par en el subarreglo aumenta, por lo que actualizamos el arreglo y agregamos 1 a cada rango. El índice i que se va a actualizar forma parte del árbol de segmentos.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation to find
// number of Even Parity numbers
// in a subarray and performing updates
 
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 1000
 
// Function that returns true if count
// of set bits in x is even
bool isEvenParity(int x)
{
    // parity will store the
    // count of set bits
    int parity = 0;
    while (x != 0) {
        if (x & 1)
            parity++;
        x = x >> 1;
    }
 
    if (parity % 2 == 0)
        return true;
    else
        return false;
}
 
// A utility function to get
// the middle index
int getMid(int s, int e)
{
    return s + (e - s) / 2;
}
 
// Recursive function to get the number
// of Even Parity numbers in a given range
int queryEvenParityUtil(
    int* segmentTree, int segmentStart,
    int segmentEnd, int queryStart,
    int queryEnd, int index)
{
    // If segment of this node is a part
    // of given range, then return
    // the number of Even Parity numbers
    // in the segment
    if (queryStart <= segmentStart
        && queryEnd >= segmentEnd)
        return segmentTree[index];
 
    // If segment of this node
    // is outside the given range
    if (segmentEnd < queryStart
        || segmentStart > queryEnd)
        return 0;
 
    // If a part of this segment
    // overlaps with the given range
    int mid = getMid(segmentStart, segmentEnd);
    return queryEvenParityUtil(
               segmentTree, segmentStart, mid,
               queryStart, queryEnd, 2 * index + 1)
           + queryEvenParityUtil(
                 segmentTree, mid + 1, segmentEnd,
                 queryStart, queryEnd, 2 * index + 2);
}
 
// Recursive function to update
// the nodes which have the given
// index in their range
void updateValueUtil(
    int* segmentTree, int segmentStart,
    int segmentEnd, int i, int diff, int si)
{
    // Base Case:
    if (i < segmentStart || i > segmentEnd)
        return;
 
    // If the input index is in range
    // of this node, then update the value
    // of the node and its children
    segmentTree[si] = segmentTree[si] + diff;
    if (segmentEnd != segmentStart) {
 
        int mid = getMid(
            segmentStart, segmentEnd);
        updateValueUtil(
            segmentTree, segmentStart,
            mid, i, diff, 2 * si + 1);
        updateValueUtil(
            segmentTree, mid + 1, segmentEnd,
            i, diff, 2 * si + 2);
    }
}
 
// Function to update a value in the
// input array and segment tree
void updateValue(int arr[], int* segmentTree,
                 int n, int i, int new_val)
{
    // Check for erroneous input index
    if (i < 0 || i > n - 1) {
        printf("Invalid Input");
        return;
    }
 
    int diff, oldValue;
 
    oldValue = arr[i];
 
    // Update the value in array
    arr[i] = new_val;
 
    // Case 1: Old and new values
    // both are Even Parity numbers
    if (isEvenParity(oldValue)
        && isEvenParity(new_val))
        return;
 
    // Case 2: Old and new values
    // both not Even Parity numbers
    if (!isEvenParity(oldValue)
        && !isEvenParity(new_val))
        return;
 
    // Case 3: Old value was Even Parity,
    // new value is non Even Parity
    if (isEvenParity(oldValue)
        && !isEvenParity(new_val)) {
        diff = -1;
    }
 
    // Case 4: Old value was non Even Parity,
    // new_val is Even Parity
    if (!isEvenParity(oldValue)
        && !isEvenParity(new_val)) {
        diff = 1;
    }
 
    // Update the values of
    // nodes in segment tree
    updateValueUtil(segmentTree, 0,
                    n - 1, i, diff, 0);
}
 
// Return number of Even Parity numbers
void queryEvenParity(int* segmentTree,
                     int n, int queryStart,
                     int queryEnd)
{
    int EvenParityInRange
        = queryEvenParityUtil(
            segmentTree, 0, n - 1,
            queryStart, queryEnd, 0);
 
    cout << EvenParityInRange << "\n";
}
 
// Recursive function that constructs
// Segment Tree for the given array
int constructSTUtil(int arr[],
                    int segmentStart,
                    int segmentEnd,
                    int* segmentTree,
                    int si)
{
    // If there is one element in array,
    // check if it is Even Parity number
    // then store 1 in the segment tree
    // else store 0 and return
    if (segmentStart == segmentEnd) {
 
        // if arr[segmentStart] is
        // Even Parity number
        if (isEvenParity(arr[segmentStart]))
            segmentTree[si] = 1;
        else
            segmentTree[si] = 0;
 
        return segmentTree[si];
    }
 
    // If there are more than one elements,
    // then recur for left and right subtrees
    // and store the sum of the
    // two values in this node
    int mid = getMid(segmentStart,
                     segmentEnd);
    segmentTree[si]
        = constructSTUtil(
              arr, segmentStart, mid,
              segmentTree, si * 2 + 1)
          + constructSTUtil(
                arr, mid + 1, segmentEnd,
                segmentTree, si * 2 + 2);
    return segmentTree[si];
}
 
// Function to construct a segment
// tree from given array
int* constructST(int arr[], int n)
{
    // Height of segment tree
    int x = (int)(ceil(log2(n)));
 
    // Maximum size of segment tree
    int max_size = 2 * (int)pow(2, x) - 1;
 
    int* segmentTree = new int[max_size];
 
    // Fill the allocated memory st
    constructSTUtil(arr, 0, n - 1,
                    segmentTree, 0);
 
    // Return the constructed segment tree
    return segmentTree;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 18, 15, 8, 9, 14, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Build segment tree from given array
    int* segmentTree = constructST(arr, n);
 
    // Query 1: Query(start = 0, end = 4)
    int start = 0;
    int end = 4;
    queryEvenParity(segmentTree, n, start, end);
 
    // Query 2: Update(i = 3, x = 11),
    // i.e Update a[i] to x
    int i = 3;
    int x = 11;
    updateValue(arr, segmentTree, n, i, x);
 
    // Query 3: Query(start = 0, end = 4)
    start = 0;
    end = 4;
    queryEvenParity(
        segmentTree, n, start, end);
 
    return 0;
}

// C# implementation to find
// number of Even Parity numbers
// in a subarray and performing updates
using System;
 
class GFG{
 
public static int MAX = 1000;
 
// Function that returns true if count
// of set bits in x is even
static bool isEvenParity(int x)
{
     
    // parity will store the
    // count of set bits
    int parity = 0;
     
    while (x != 0)
    {
        if ((x & 1) != 0)
            parity++;
             
        x = x >> 1;
    }
 
    if (parity % 2 == 0)
        return true;
    else
        return false;
}
 
// A utility function to get
// the middle index
static int getMid(int s, int e)
{
    return s + (e - s) / 2;
}
 
// Recursive function to get the number
// of Even Parity numbers in a given range
static int queryEvenParityUtil(int[] segmentTree,
                               int segmentStart,
                               int segmentEnd,
                               int queryStart,
                               int queryEnd, int index)
{
     
    // If segment of this node is a part
    // of given range, then return
    // the number of Even Parity numbers
    // in the segment
    if (queryStart <= segmentStart &&
        queryEnd >= segmentEnd)
        return segmentTree[index];
 
    // If segment of this node
    // is outside the given range
    if (segmentEnd < queryStart ||
        segmentStart > queryEnd)
        return 0;
 
    // If a part of this segment
    // overlaps with the given range
    int mid = getMid(segmentStart, segmentEnd);
    return queryEvenParityUtil(segmentTree, segmentStart,
                               mid, queryStart, queryEnd,
                               2 * index + 1) +
           queryEvenParityUtil(segmentTree, mid + 1,
                               segmentEnd, queryStart,
                               queryEnd, 2 * index + 2);
}
 
// Recursive function to update
// the nodes which have the given
// index in their range
static void updateValueUtil(int[] segmentTree,
                            int segmentStart,
                            int segmentEnd, int i,
                            int diff, int si)
{
     
    // Base Case:
    if (i < segmentStart || i > segmentEnd)
        return;
 
    // If the input index is in range
    // of this node, then update the value
    // of the node and its children
    segmentTree[si] = segmentTree[si] + diff;
     
    if (segmentEnd != segmentStart)
    {
        int mid = getMid(segmentStart, segmentEnd);
        updateValueUtil(segmentTree, segmentStart, mid,
                        i, diff, 2 * si + 1);
        updateValueUtil(segmentTree, mid + 1,
                        segmentEnd, i, diff,
                        2 * si + 2);
    }
}
 
// Function to update a value in the
// input array and segment tree
static void updateValue(int[] arr, int[] segmentTree,
                        int n, int i, int new_val)
{
     
    // Check for erroneous input index
    if (i < 0 || i > n - 1)
    {
        Console.WriteLine("Invalid Input");
        return;
    }
 
    int diff = 0, oldValue = 0;
 
    oldValue = arr[i];
 
    // Update the value in array
    arr[i] = new_val;
 
    // Case 1: Old and new values
    // both are Even Parity numbers
    if (isEvenParity(oldValue) &&
        isEvenParity(new_val))
        return;
 
    // Case 2: Old and new values
    // both not Even Parity numbers
    if (!isEvenParity(oldValue) &&
        !isEvenParity(new_val))
        return;
 
    // Case 3: Old value was Even Parity,
    // new value is non Even Parity
    if (isEvenParity(oldValue) &&
       !isEvenParity(new_val))
    {
        diff = -1;
    }
 
    // Case 4: Old value was non Even Parity,
    // new_val is Even Parity
    if (!isEvenParity(oldValue) &&
        !isEvenParity(new_val))
    {
        diff = 1;
    }
 
    // Update the values of
    // nodes in segment tree
    updateValueUtil(segmentTree, 0, n - 1, i, diff, 0);
}
 
// Return number of Even Parity numbers
static void queryEvenParity(int[] segmentTree, int n,
                            int queryStart,
                            int queryEnd)
{
    int EvenParityInRange = queryEvenParityUtil(
        segmentTree, 0, n - 1, queryStart, queryEnd, 0);
 
    Console.WriteLine(EvenParityInRange);
}
 
// Recursive function that constructs
// Segment Tree for the given array
static int constructSTUtil(int[] arr, int segmentStart,
                           int segmentEnd,
                           int[] segmentTree, int si)
{
     
    // If there is one element in array,
    // check if it is Even Parity number
    // then store 1 in the segment tree
    // else store 0 and return
    if (segmentStart == segmentEnd)
    {
         
        // if arr[segmentStart] is
        // Even Parity number
        if (isEvenParity(arr[segmentStart]))
            segmentTree[si] = 1;
        else
            segmentTree[si] = 0;
 
        return segmentTree[si];
    }
 
    // If there are more than one elements,
    // then recur for left and right subtrees
    // and store the sum of the
    // two values in this node
    int mid = getMid(segmentStart, segmentEnd);
    segmentTree[si] = constructSTUtil(arr, segmentStart, mid,
                                      segmentTree, si * 2 + 1) +
                      constructSTUtil(arr, mid + 1, segmentEnd,
                                      segmentTree, si * 2 + 2);
    return segmentTree[si];
}
 
// Function to construct a segment
// tree from given array
static int[] constructST(int[] arr, int n)
{
     
    // Height of segment tree
    int x = (int)(Math.Ceiling(Math.Log(n, 2)));
 
    // Maximum size of segment tree
    int max_size = 2 * (int)Math.Pow(2, x) - 1;
 
    int[] segmentTree = new int[max_size];
 
    // Fill the allocated memory st
    constructSTUtil(arr, 0, n - 1, segmentTree, 0);
 
    // Return the constructed segment tree
    return segmentTree;
}
 
// Driver Code
public static void Main()
{
    int[] arr = { 18, 15, 8, 9, 14, 5 };
    int n = arr.Length;
 
    // Build segment tree from given array
    int[] segmentTree = constructST(arr, n);
 
    // Query 1: Query(start = 0, end = 4)
    int start = 0;
    int end = 4;
    queryEvenParity(segmentTree, n, start, end);
 
    // Query 2: Update(i = 3, x = 11),
    // i.e Update a[i] to x
    int i = 3;
    int x = 11;
    updateValue(arr, segmentTree, n, i, x);
 
    // Query 3: Query(start = 0, end = 4)
    start = 0;
    end = 4;
    queryEvenParity(segmentTree, n, start, end);
}
}
 
// This code is contributed by ukasp

3
2