Programa C++ para encontrar la suma de la array usando Bitwise OR después de dividir la array dada en dos mitades después de K cambios circulares

Dada una array A[] de longitud N , donde N es un número par, la tarea es responder Q consultas independientes donde cada consulta consiste en un número entero positivo K que representa el número de desplazamientos circulares realizados en la array y encontrar la suma de elementos realizando la operación Bitwise OR en la array dividida.
Nota: Cada consulta comienza con la array original.
Ejemplos: 
 

Entrada: A[] = {12, 23, 4, 21, 22, 76}, Q = 1, K = 2 
Salida: 117 
Explicación: 
Dado que K es 2, array modificada A[]={22, 76, 12, 23, 4, 21}. 
OR bit a bit de la primera mitad del arreglo = (22 | 76 | 12) = 94 
OR bit a bit de la segunda mitad del arreglo = (21 | 23 | 4) = 23  La
suma de los valores OR es 94 + 23 = 117
Entrada: A[] = {7, 44, 19, 86, 65, 39, 75, 101}, Q = 1, K = 4 
Salida: 238 
Dado que K es 4, array modificada A[]={65, 39, 75, 101, 7, 44, 19, 86}. 
OR bit a bit de la primera mitad del arreglo = 111 
OR bit a bit de la segunda mitad del arreglo = 127 
La suma de los valores OR es 111 + 127 = 238 
 

Enfoque ingenuo: 
para resolver el problema mencionado anteriormente, el enfoque más simple es desplazar cada elemento de la array en K % (N / 2) y luego atravesar la array para calcular el OR de las dos mitades para cada consulta. Pero este método no es eficiente y, por lo tanto, puede optimizarse aún más.
Enfoque eficiente: 
para optimizar el enfoque mencionado anteriormente, podemos tomar la ayuda de la estructura de datos  del árbol de segmentos .
 

Observación: 
 

• Podemos observar que después de exactamente N / 2 desplazamientos circulares a la derecha, las dos mitades de la array se vuelven iguales a las de la array original. Esto reduce efectivamente el número de rotaciones a K % (N / 2) .
• Realizar un desplazamiento circular a la derecha consiste básicamente en desplazar el último elemento de la array hacia el frente. Entonces, para cualquier número entero positivo X , realizar X desplazamientos circulares a la derecha es igual a desplazar los últimos X elementos de la array al frente.

Los siguientes son los pasos para resolver el problema: 
 

• Construya un árbol de segmentos para la array original A[] y asigne una variable, digamos i = K % (N / 2) .
• Luego, para cada consulta, usamos el árbol de segmentos de encontrar el OR bit a bit; es decir OR bit a bit de i elementos del final OR bit a bit OR del primero (N / 2) – i – 1 elementos.
• Luego calcule el OR bit a bit de los elementos en el rango [(N / 2) – i, N – i – 1] .
• Sume los dos resultados para obtener la respuesta de la i-ésima consulta.

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

// C++ Program to find Bitwise OR of two
// equal halves of an array after performing
// K right circular shifts
#include <bits/stdc++.h>
const int MAX = 100005;
using namespace std;
 
// Array for storing
// the segment tree
int seg[4 * MAX];
 
// Function to build the segment tree
void build(int node, int l, int r, int a[])
{
    if (l == r)
        seg[node] = a[l];
 
    else {
        int mid = (l + r) / 2;
 
        build(2 * node, l, mid, a);
        build(2 * node + 1, mid + 1, r, a);
 
        seg[node] = (seg[2 * node]
                     | seg[2 * node + 1]);
    }
}
 
// Function to return the OR
// of elements in the range [l, r]
int query(int node, int l, int r,
          int start, int end, int a[])
{
    // Check for out of bound condition
    if (l > end or r < start)
        return 0;
 
    if (start <= l and r <= end)
        return seg[node];
 
    // Find middle of the range
    int mid = (l + r) / 2;
 
    // Recurse for all the elements in array
    return ((query(2 * node, l, mid,
                   start, end, a))
            | (query(2 * node + 1, mid + 1,
                     r, start, end, a)));
}
 
// Function to find the OR sum
void orsum(int a[], int n, int q, int k[])
{
    // Function to build the segment Tree
    build(1, 0, n - 1, a);
 
    // Loop to handle q queries
    for (int j = 0; j < q; j++) {
        // Effective number of
        // right circular shifts
        int i = k[j] % (n / 2);
 
        // Calculating the OR of
        // the two halves of the
        // array from the segment tree
 
        // OR of second half of the
        // array [n/2-i, n-1-i]
        int sec = query(1, 0, n - 1,
                        n / 2 - i, n - i - 1, a);
 
        // OR of first half of the array
        // [n-i, n-1]OR[0, n/2-1-i]
        int first = (query(1, 0, n - 1, 0,
                           n / 2 - 1 - i, a)
                     | query(1, 0, n - 1,
                             n - i, n - 1, a));
 
        int temp = sec + first;
 
        // Print final answer to the query
        cout << temp << endl;
    }
}
 
// Driver Code
int main()
{
 
    int a[] = { 7, 44, 19, 86, 65, 39, 75, 101 };
    int n = sizeof(a) / sizeof(a[0]);
 
    int q = 2;
 
    int k[q] = { 4, 2 };
 
    orsum(a, n, q, k);
 
    return 0;
}

238
230

Complejidad de tiempo: O(N + Q*logN)

Espacio auxiliar: O(4*MAX)

¡ Consulte el artículo completo sobre Encontrar la suma de la array usando Bitwise O después de dividir la array dada en dos mitades después de K cambios circulares para obtener más detalles!