Introduction

Hi everyone, because we noticed there was no good tutorial in English explaining this idea, KrowSavcik and I have decided to write a tutorial blog on it!

This idea finds the values of each element from a binary array using $$$O(N / log(N))$$$ sum queries, more specifically it solves problems of the type:

Given a binary array $$$b$$$ (an array consisting only of zeroes and ones) of $$$n$$$ elements, you can ask queries of the following format:

What is the sum of the subsequence of the values on positions: $$$p_1, p_2, ..., p_k$$$. In other words you will give the subsequence $$$p_1, p_2, ..., p_k$$$ to the interaction and it will return you the value of ($$$b_{p_1} + b_{p_2} + ... + b_{p_k}$$$).

And after asking $$$O(N / log(N))$$$ queries we should be able to tell the value of each index.

The technique was mentioned here too but it was not as detailed.

Concept

The idea is to use a divide and conquer like approach. Because it's not an intuitive concept, firstly I will have to add some simple notations, so it will be easier to understand it.

• $$$x_i$$$ — refers to the position $$$i$$$
• $$$A$$$ — any capital letter (except S) refers to a set of points $$$x_i$$$
• $$$v_{A} = \sum b_{i}$$$ for $$$x_i \in A$$$
• $$$S_i$$$ — Set of queries, where a query can be represented as a set of points

As it is a divide and conquer like approach we will work with layers. Let's say that for layer $$$k$$$ we need $$$2^k$$$ queries and that from it we can get the value of $$$f_k$$$ bits. Than $$$f_{k+1} = 2 f_k + 2^k - 1$$$.

The block $$$f_{k+1}$$$ is formed from $$$2$$$ blocks of size $$$f_k$$$ and $$$2^k -1$$$ elements.