Consultas de suma de subconjuntos en un rango usando Bitset

Dada una array[] de N enteros positivos y M consultas. Cada consulta consta de dos números enteros L y R representados por un rango. Para cada consulta, encuentre el recuento de números que se encuentran en el rango dado que se puede expresar como la suma de cualquier subconjunto de la array dada.

Requisito previo: consultas de suma de subconjuntos utilizando
ejemplos de conjuntos de bits:

Entrada: arr[] = { 1, 2, 2, 3, 5 }, M = 4
L = 1, R = 2
L = 1, R = 5
L = 3, R = 6
L = 9, R = 30
Salida :
2
5
4
5
Explicación: para la primera consulta, en el rango [1, 2] todos los números, es decir, 1 y 2, se pueden expresar como una suma de subconjuntos, 1 como 1, 2 como 2. Para la segunda consulta, en el rango [1 , 5] todos los números, es decir, 1, 2, 3, 4 y 5 se pueden expresar como suma de subconjuntos, 1 como 1, 2 como 2, 3 como 3, 4 como 2 + 2 o 1 + 3, 5 como 5. Para el tercera consulta, en el rango [3, 6], todos los números, es decir, 3, 4, 5 y 6, se pueden expresar como suma de subconjuntos. Para la última consulta, solo los números 9, 10, 11, 12, 13 se pueden expresar como suma de subconjuntos, 9 como 5 + 2 + 2, 10 como 5 + 2 + 2 + 1, 11 como 5 + 3 + 2 + 1 , 12 como 5 + 3 + 2 + 2 y 13 como 5 + 3 + 2 + 2 + 1.

Enfoque: la idea es usar un conjunto de bits e iterar sobre la array para representar todas las sumas de subconjuntos posibles. El estado actual del conjunto de bits se define mediante la operación OR con el estado anterior del conjunto de bits desplazado a la izquierda X veces, donde X es el elemento actual procesado en la array. Para responder a las consultas en tiempo O(1), podemos precalcular el conteo de números hasta cada número y para un rango [L, R], la respuesta sería pre[R] – pre[L – 1] , donde pre[] es la array precalculada.

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

// CPP Program to answer subset
// sum queries in a given range
#include <bits/stdc++.h>
using namespace std;
  
const int MAX = 1001;
bitset<MAX> bit;
  
// precomputation array
int pre[MAX];
  
// structure to represent query
struct que {
    int L, R;
};
  
void answerQueries(int Q, que Queries[], int N,
                   int arr[])
{
    // Setting bit at 0th position as 1
    bit[0] = 1;
    for (int i = 0; i < N; i++)
        bit |= (bit << arr[i]);
  
    // Precompute the array
    for (int i = 1; i < MAX; i++)
        pre[i] = pre[i - 1] + bit[i];
  
    // Answer Queries
    for (int i = 0; i < Q; i++) {
        int l = Queries[i].L;
        int r = Queries[i].R;
        cout << pre[r] - pre[l - 1] << endl;
    }
}
  
// Driver Code to test above function
int main()
{
    int arr[] = { 1, 2, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int M = 4;
    que Queries[M];
    Queries[0].L = 1, Queries[0].R = 2;
    Queries[1].L = 1, Queries[1].R = 5;
    Queries[2].L = 3, Queries[2].R = 6;
    Queries[3].L = 9, Queries[3].R = 30;
    answerQueries(M, Queries, N, arr);
    return 0;
}

2
5
4
5

Complejidad de tiempo: cada consulta se puede responder en tiempo O (1) y el cálculo previo requiere tiempo O (MAX).