Consultas para OR bit a bit en el rango de índice [L, R] de la array dada

Dada una array arr[] de N y Q consultas que consisten en un rango [L, R] . la tarea es encontrar el OR bit a bit de todos los elementos en ese rango de índice.
Ejemplos: 
 

Entrada: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}} 
Salida: 
3 
7 
1 O 3 = 3 
2 O 3 O 4 = 7
Entrada: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}} 
Salida: 
7 
7 
 

Enfoque ingenuo: iterar a través del rango y encontrar OR bit a bit de todos los números en ese rango. Esto llevará O(n) tiempo para cada consulta.
Enfoque eficiente: si observamos los números enteros como un número binario, podemos ver fácilmente que la condición para que se establezca el i – ^ésimo bit de nuestra respuesta es que se debe establecer el i ^-ésimo bit de cualquiera de los enteros en el rango [L, R] . . 
Entonces, calcularemos el conteo de prefijos para cada bit. Usaremos esto para encontrar el número de enteros en el rango con i ^-ésimo bit establecido. Si es mayor que 0 , también se establecerá el i ^-ésimo bit de nuestra respuesta.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
#define MAX 100000
#define bitscount 32
using namespace std;
 
// Array to store bit-wise
// prefix count
int prefix_count[bitscount][MAX];
 
// Function to find the prefix sum
void findPrefixCount(int arr[], int n)
{
 
    // Loop for each bit
    for (int i = 0; i < bitscount; i++) {
        // Loop to find prefix count
        prefix_count[i][0] = ((arr[0] >> i) & 1);
        for (int j = 1; j < n; j++) {
            prefix_count[i][j] = ((arr[j] >> i) & 1);
            prefix_count[i][j] += prefix_count[i][j - 1];
        }
    }
}
 
// Function to answer query
int rangeOr(int l, int r)
{
 
    // To store the answer
    int ans = 0;
 
    // Loop for each bit
    for (int i = 0; i < bitscount; i++) {
        // To store the number of variables
        // with ith bit set
        int x;
        if (l == 0)
            x = prefix_count[i][r];
        else
            x = prefix_count[i][r]
                - prefix_count[i][l - 1];
 
        // Condition for ith bit
        // of answer to be set
        if (x != 0)
            ans = (ans | (1 << i));
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 7, 5, 3, 5, 2, 3 };
    int n = sizeof(arr) / sizeof(int);
 
    findPrefixCount(arr, n);
 
    int queries[][2] = { { 1, 3 }, { 4, 5 } };
    int q = sizeof(queries) / sizeof(queries[0]);
 
    for (int i = 0; i < q; i++)
        cout << rangeOr(queries[i][0],
                        queries[i][1])
             << endl;
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
     
static int MAX = 100000;
static int bitscount = 32;
 
// Array to store bit-wise
// prefix count
static int [][]prefix_count = new int [bitscount][MAX];
 
// Function to find the prefix sum
static void findPrefixCount(int arr[], int n)
{
 
    // Loop for each bit
    for (int i = 0; i < bitscount; i++)
    {
        // Loop to find prefix count
        prefix_count[i][0] = ((arr[0] >> i) & 1);
        for (int j = 1; j < n; j++)
        {
            prefix_count[i][j] = ((arr[j] >> i) & 1);
            prefix_count[i][j] += prefix_count[i][j - 1];
        }
    }
}
 
// Function to answer query
static int rangeOr(int l, int r)
{
 
    // To store the answer
    int ans = 0;
 
    // Loop for each bit
    for (int i = 0; i < bitscount; i++)
    {
        // To store the number of variables
        // with ith bit set
        int x;
        if (l == 0)
            x = prefix_count[i][r];
        else
            x = prefix_count[i][r]
                - prefix_count[i][l - 1];
 
        // Condition for ith bit
        // of answer to be set
        if (x != 0)
            ans = (ans | (1 << i));
    }
 
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
     
    int arr[] = { 7, 5, 3, 5, 2, 3 };
    int n = arr.length;
    findPrefixCount(arr, n);
    int queries[][] = { { 1, 3 }, { 4, 5 } };
    int q = queries.length;
    for (int i = 0; i < q; i++)
            System.out.println (rangeOr(queries[i][0],queries[i][1]));
 
}
}
 
// This code is contributed by Tushil.

# Python3 implementation of the approach
 
import numpy as np
 
MAX = 100000
bitscount = 32
 
# Array to store bit-wise
# prefix count
prefix_count = np.zeros((bitscount,MAX));
 
# Function to find the prefix sum
def findPrefixCount(arr, n) :
 
    # Loop for each bit
    for i in range(0, bitscount) :
        # Loop to find prefix count
        prefix_count[i][0] = ((arr[0] >> i) & 1);
         
        for j in range(1, n) :
            prefix_count[i][j] = ((arr[j] >> i) & 1);
            prefix_count[i][j] += prefix_count[i][j - 1];
 
# Function to answer query
def rangeOr(l, r) :
 
    # To store the answer
    ans = 0;
 
    # Loop for each bit
    for i in range(bitscount) :
         
        # To store the number of variables
        # with ith bit set
        x = 0;
         
        if (l == 0) :
            x = prefix_count[i][r];
        else :
            x = prefix_count[i][r] - prefix_count[i][l - 1];
 
        # Condition for ith bit
        # of answer to be set
        if (x != 0) :
            ans = (ans | (1 << i));
             
    return ans;
 
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 7, 5, 3, 5, 2, 3 ];
    n = len(arr);
 
    findPrefixCount(arr, n);
 
    queries = [ [ 1, 3 ], [ 4, 5 ] ];
     
    q = len(queries);
 
    for i in range(q) :
        print(rangeOr(queries[i][0], queries[i][1]));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
static int MAX = 100000;
static int bitscount = 32;
 
// Array to store bit-wise
// prefix count
static int [,]prefix_count = new int [bitscount,MAX];
 
// Function to find the prefix sum
static void findPrefixCount(int []arr, int n)
{
 
    // Loop for each bit
    for (int i = 0; i < bitscount; i++)
    {
        // Loop to find prefix count
        prefix_count[i,0] = ((arr[0] >> i) & 1);
        for (int j = 1; j < n; j++)
        {
            prefix_count[i,j] = ((arr[j] >> i) & 1);
            prefix_count[i,j] += prefix_count[i,j - 1];
        }
    }
}
 
// Function to answer query
static int rangeOr(int l, int r)
{
 
    // To store the answer
    int ans = 0;
 
    // Loop for each bit
    for (int i = 0; i < bitscount; i++)
    {
        // To store the number of variables
        // with ith bit set
        int x;
        if (l == 0)
            x = prefix_count[i,r];
        else
            x = prefix_count[i,r]
                - prefix_count[i,l - 1];
 
        // Condition for ith bit
        // of answer to be set
        if (x != 0)
            ans = (ans | (1 << i));
    }
 
    return ans;
}
 
// Driver code
public static void Main (String[] args)
{
     
    int []arr = { 7, 5, 3, 5, 2, 3 };
    int n = arr.Length;
    findPrefixCount(arr, n);
    int [,]queries = { { 1, 3 }, { 4, 5 } };
    int q = queries.GetLength(0);
    for (int i = 0; i < q; i++)
            Console.WriteLine(rangeOr(queries[i,0],queries[i,1]));
 
}
}
 
// This code is contributed by 29AjayKumar

<?php
 
// PHP implementation of the approach
$MAX= 100000;
$bitscount = 32;
 
// Array to store bit-wise
// prefix count
$prefix_count = array_fill(0,$bitscount,array_fill(0,$MAX,NULL));
 
// Function to find the prefix sum
function findPrefixCount(&$arr, $n)
{
    global $MAX,$bitscount,$prefix_count;
 
    // Loop for each bit
    for ($i = 0; $i < $bitscount; $i++)
    {
        // Loop to find prefix count
        $prefix_count[$i][0] = (($arr[0] >> $i) & 1);
        for ($j = 1; $j < $n; $j++)
        {
            $prefix_count[$i][$j] = (($arr[$j] >> $i) & 1);
            $prefix_count[$i][$j] += $prefix_count[$i][$j - 1];
        }
    }
}
 
// Function to answer query
function rangeOr($l, $r)
{
    global $MAX,$bitscount,$prefix_count;
     
    // To store the answer
    $ans = 0;
 
    // Loop for each bit
    for ($i = 0; $i < $bitscount; $i++)
    {
        // To store the number of variables
        // with ith bit set
         
        if ($l == 0)
            $x = $prefix_count[$i][$r];
        else
            $x = $prefix_count[$i][$r]
                - $prefix_count[$i][l - 1];
 
        // Condition for ith bit
        // of answer to be set
        if ($x != 0)
            $ans = ($ans | (1 << $i));
    }
 
    return $ans;
}
 
    // Driver code
    $arr =array( 7, 5, 3, 5, 2, 3 );
    $n = sizeof($arr) / sizeof($arr[0]);
 
    findPrefixCount($arr, $n);
 
    $queries = array(array( 1, 3 ), array( 4, 5 ));
    $q = sizeof($queries) / sizeof($queries[0]);
 
    for ($i = 0; $i < $q; $i++)
        echo rangeOr($queries[$i][0],
                        $queries[$i][1])."\n";
 
    return 0;
     
    // This code is contributed by ChitraNayal
?>

<script>   
    // Javascript implementation of the approach
     
    let MAX = 100000;
    let bitscount = 32;
 
    // Array to store bit-wise
    // prefix count
    let prefix_count = new Array(bitscount);
    for (let i = 0; i < bitscount; i++)
    {
        prefix_count[i] = new Array(MAX);   
        for (let j = 0; j < MAX; j++)
        {
            prefix_count[i][j] = 0;
        }
    }
 
    // Function to find the prefix sum
    function findPrefixCount(arr, n)
    {
 
        // Loop for each bit
        for (let i = 0; i < bitscount; i++)
        {
            // Loop to find prefix count
            prefix_count[i][0] = ((arr[0] >> i) & 1);
            for (let j = 1; j < n; j++)
            {
                prefix_count[i][j] = ((arr[j] >> i) & 1);
                prefix_count[i][j] += prefix_count[i][j - 1];
            }
        }
    }
 
    // Function to answer query
    function rangeOr(l, r)
    {
 
        // To store the answer
        let ans = 0;
 
        // Loop for each bit
        for (let i = 0; i < bitscount; i++)
        {
            // To store the number of variables
            // with ith bit set
            let x;
            if (l == 0)
                x = prefix_count[i][r];
            else
                x = prefix_count[i][r]
                    - prefix_count[i][l - 1];
 
            // Condition for ith bit
            // of answer to be set
            if (x != 0)
                ans = (ans | (1 << i));
        }
 
        return ans;
    }
     
    let arr = [ 7, 5, 3, 5, 2, 3 ];
    let n = arr.length;
    findPrefixCount(arr, n);
    let queries = [ [ 1, 3 ], [ 4, 5 ] ];
    let q = queries.length;
    for (let i = 0; i < q; i++)
            document.write(rangeOr(queries[i][0],queries[i][1]) + "</br>");
 
</script>

7
3

La complejidad del tiempo para el cálculo previo es O(n) y cada consulta se puede responder en O(1)

Espacio auxiliar: O (bitscount * MAX)