Programa Javascript para 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

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:
 

<script>
// javascript program to find Bitwise OR of two
// equal halves of an array after performing
// K right circular shifts
    const MAX = 100005;
 
    // Array for storing
    // the segment tree
    var seg = Array(4 * MAX).fill(0);
 
    // Function to build the segment tree
    function build(node , l , r , a) {
        if (l == r)
            seg[node] = a[l];
 
        else {
            var mid = parseInt((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]
    function query(node , l , r , start , end , a) {
 
        // Check for out of bound condition
        if (l > end || r < start)
            return 0;
 
        if (start <= l && r <= end)
            return seg[node];
 
        // Find middle of the range
        var mid = parseInt((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
    function orsum(a , n , q , k) {
 
        // Function to build the segment Tree
        build(1, 0, n - 1, a);
 
        // Loop to handle q queries
        for (j = 0; j < q; j++) {
 
            // Effective number of
            // right circular shifts
            var 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]
            var 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]
            var first = (query(1, 0, n - 1, 0, n / 2 - 1 - i, a) | query(1, 0, n - 1, n - i, n - 1, a));
 
            var temp = sec + first;
 
            // Print final answer to the query
            document.write(temp + "<br/>");
        }
    }
 
    // Driver Code
        var a = [ 7, 44, 19, 86, 65, 39, 75, 101 ];
        var n = a.length;
        var q = 2;
 
        var k = [ 4, 2 ];
 
        orsum(a, n, q, k);
 
// This code is contributed by Rajput-Ji.
</script>

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!