The problem we are trying to solve sounds as follows: You are given $N$ bits. Find the value of each bit.  We will show a technique which enables finding the values of $N$ bits using $O(\frac{N}{\log N})$ subsequence-sum queries. The algorithm consists of two phases: Constructing the queries for each layer and using the queries for a particular layer to get the value of every bit.  We described the following technique in this blog [1], which was inspired by this article [2]. It should be noted that this number of queries is indeed the optimal one for finding all $N$ bits of a binary array, since each subsequence-sum queries offers us at most $\log_{2} N$ bits of information.

Problema pe care încercăm să o rezolvăm sună astfel:  vi se oferă $N$ biți. Găsiți valoarea fiecărui bit. Vom prezenta o tehnică care permite aflarea valorilor a $N$ biți folosind $O(\frac{N}{\log N})$ interogări de sume pe subsecvențe. Algoritmul se divide în două faze: construirea interogărilor pentru fiecare strat și utilizarea acestora pentru un strat particular pentru a obține valoarea fiecărui bit. Am descris această tehnică în articolul de blog [1], care dezvoltă rezultatele din articolul lui Zhenting Zhu din universitatea Tsinghua [2]. Trebuie să menționăm faptul că acest număr de interogări este într-adevăr optimal pentru găsirea tuturor $N$ biților unui șir binar, deoarece fiecare interogare de sumă de subsecvențe ne oferă cel mult $\log_{2} N$ biți de informație.