Consultas para minimizar la suma agregada a rangos dados en una array para hacer que su Bitwise AND no sea cero

Dada una array arr[] que consta de N enteros, una array Q[][] que consta de consultas de la forma {l, r} . Para cada consulta {l, r} , la tarea es determinar la suma mínima de todos los valores que deben agregarse a cada elemento de array en ese rango de modo que el AND bit a bit de todos los números en ese rango exceda 0 . 
Nota: Se pueden agregar diferentes valores a diferentes enteros en el rango dado. 

Ejemplos:

Entrada: arr[] = {1, 2, 4, 8}, Q[][] = {{1, 4}, {2, 3}, {1, 3}}
Salida: 3 2 2
Explicación:  representación binaria de elementos de array son los siguientes:
1 – 0001
2 – 0010
4 – 0100
8 – 1000
Para la primera consulta {1, 4}, agregue 1 a todos los números presentes en el rango excepto el primer número. Por lo tanto, Bitwise AND = (1 & 3 & 5 & 9) = 1 y suma mínima de elementos agregados = 3.
Para la segunda consulta {2, 3}, agregue 2 al 3er elemento. Por lo tanto, AND bit a bit = (2 y 6) = 2 y suma mínima de elementos agregados = 2.
Para la tercera consulta {1, 3}, agregue 1 a los elementos 2 y 3. Por lo tanto, Bitwise AND = (1 & 3 & 5) = 1 y suma mínima de elementos agregados = 2.

Entrada: arr[] = {4, 6, 5, 3}, Q[][] = {{1, 4}}
Salida: 1
Explicación: La forma óptima de hacer que Bitwise AND no sea cero es agregar 1 a último elemento Por lo tanto, AND bit a bit = (4 & 6 & 5 & 4) = 4 y suma mínima de elementos sumados = 1.

Enfoque: la idea es observar primero que el AND bit a bit de todos los enteros en el rango [l, r] solo puede ser distinto de cero si se establece un bit en un índice particular para cada entero en ese rango. 
Siga los pasos a continuación para resolver el problema:

1. Inicialice un vector 2D pre donde pre[i][j] almacena la suma mínima de enteros que se agregarán a todos los enteros desde el índice 0 hasta el índice i de modo que, para cada uno de ellos, se establezca su j ^-ésimo bit.
2. Para cada elemento en el índice i , verifique cada uno de sus bits de j = 0 a 31 .
3. Inicialice una suma variable con 0 .
4. Si se establece el j ^-ésimo bit, actualice pre[i][j] como pre[i][j]=pre[i-1][j] e incremente la suma en 2 ^j . De lo contrario, actualice pre[i][j] = pre[i-1][j] + 2 ^j – sum donde (2 ^j -sum) es el valor que debe agregarse para establecer el j ^-ésimo bit de arr[i] .
5. Ahora, para cada consulta {l, r} , la suma mínima requerida para establecer el j ^-ésimo bit de todos los elementos en el rango dado es pre[r][j] – pre[l-1][j] .
6. Para cada consulta {l, r} , encuentre la respuesta para cada bit de j = 0 a 31 e imprima el mínimo entre ellos.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the min sum required
// to set the jth bit of all integer
void processing(vector<int> v,
                vector<vector<long long int> >& pre)
{
 
    // Number of elements
    int N = v.size();
 
    // Traverse all elements
    for (int i = 0; i < N; i++) {
 
        // Binary representation
        bitset<32> b(v[i]);
 
        long long int sum = 0;
 
        // Take previous values
        if (i != 0) {
 
            pre[i] = pre[i - 1];
        }
 
        // Processing each bit and
        // store it in 2d vector
        for (int j = 0; j < 32; j++) {
 
            if (b[j] == 1) {
 
                sum += 1ll << j;
            }
            else {
 
                pre[i][j]
                    += (1ll << j) - sum;
            }
        }
    }
}
 
// Function to print the minimum
// sum for each query
long long int
process_query(vector<vector<int> > Q,
              vector<vector<long long int> >& pre)
{
 
    // Stores the sum for each query
    vector<int> ans;
 
    for (int i = 0; i < Q.size(); i++) {
 
        // Update wrt 0-based index
        --Q[i][0], --Q[i][1];
 
        // Initizlize answer
        long long int min1 = INT_MAX;
 
        // Find minimum sum for each bit
        if (Q[i][0] == 0) {
 
            for (int j = 0; j < 32; j++) {
 
                min1 = min(pre[Q[i][1]][j], min1);
            }
        }
        else {
 
            for (int j = 0; j < 32; j++) {
 
                min1 = min(pre[Q[i][1]][j]
                               - pre[Q[i][0] - 1][j],
                           min1);
            }
        }
 
        // Store the answer for
        // each query
        ans.push_back(min1);
    }
 
    // Print the answer vector
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
}
 
// Driver Code
int main()
{
 
    // Given array
    vector<int> arr = { 1, 2, 4, 8 };
 
    // Given Queries
    vector<vector<int> > Q
        = { { 1, 4 }, { 2, 3 }, { 1, 3 } };
 
    // 2d Prefix vector
    vector<vector<long long int> > pre(
        100001, vector<long long int>(32, 0));
 
    // Preprocessing
    processing(arr, pre);
 
    // Function call for queries
    process_query(Q, pre);
 
    return 0;
}

3 2 2

Complejidad de tiempo: O(N*32 + tamaño de(Q)*32) 
Espacio auxiliar: O(N*32)