Podzadatak 1

U prvom podzadatku, za svaki upit prođemo kroz podniz za koji se traži odgovor i izvršimo bitovsku konjunkciju svih elemenata. Vremenska složenost je ~O(NQ)~.

Podzadatak 2

U drugom podzadatku u nizu su samo jedinice i nule. Primetimo da je odgovor na upit ili ~0~ ili ~1~. U ovom podzadatku napravimo prefiksne sume, tj. proverimo koliko puta se pojavljuje ~1~ do nekog indeksa ~i~. Neka je ovaj broj ~p_{i}~. Uslov da odgovor bude ~1~ je da između indeksa ~l~ i ~r~ budu sve jedinice, tj. da važi ~p_{r}-p_{l-1}=r-l+1~. Vremenska složenost je ~O(N)~.

Podzadatak 3 (kompletno rešenje)

Za kompletno rešenje neophodno je da zamislimo naše brojeve u binarnom sistemu i da primetimo da bitove ovde možemo da posmatramo nezavisno. Sada radimo sličan postupak kao i u prethodnom podzadatku, za svaki bit ~k~, nađemo u koliko brojeva do indeksa ~i~ je on ~1~. Neka je ovaj broj ~p_{k,i}~. Da bi taj bit bio ~1~ kada izvršimo konjunkciju svih elemenata, potrebno je da važi ~p_{k,r}-p_{k,l-1}=r-l+1~. Tada je odgovor na upit od ~l~ do ~r~ jednak ~\sum 2^k~, za sve ~k~ za koje važi ~p_{k,r}-p_{k,l-1}=r-l+1~. Vremenska složenost je ~O(N\log A_{i})~.