[Tutorial] Finding N bits using O(N / log(N)) sums

Revision en3, by KrowSavcik, 2022-07-23 20:17:23

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$$$
  • $$$(A)$$$ — a set in brackets is a query
  • $$$S_i$$$ — Set of queries

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. The first query is used to get the sum on $$$[f_k;2f_k)$$$ second block. Then for each non last query in $$$S_{k_1}$$$ and $$$S_{k_2}$$$ we add two new queries. First is $$$S_{k_1}[i] \cup S_{k_2}[i]$$$. Second one is $$$S_{k_1}[i] \cup [f_k;2f_k) \cap S_{k_2}[i] \cup x_{2f_k+i}$$$.

The last query is for entire range $$$[0, f_{k+1})$$$.

I think it's easy to see why we now have $$$2^{k+1}$$$ queries. The harder part is to understand why we don't lose any value in this process, and how we can solve it recursively. In fact, having answered all the $$$S_{k+1}$$$ queries, we can calculate all the $$$v_{S_{k_1}[i]}$$$ and $$$v_{S_{k_2}[i]}$$$.

Let's denote the numbers of $$$1$$$s in $$$[f_k;2f_k)$$$ with $$$c$$$. It's obvious that $$$c = S_{k+1}[0]$$$.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en18 English SlavicG 2022-07-29 12:41:24 8 Tiny change: '+ 2]} - c)$ & $1$\n\nThe ' -> '+ 2]} - c) \land 1$\n\nThe '
en17 English SlavicG 2022-07-29 12:40:12 12 Tiny change: 'that $c = S[0]$. We ' -> 'that $c = v_S[0]$. We '
en16 English KrowSavcik 2022-07-24 13:28:54 62 Minor correction
en15 English SlavicG 2022-07-24 12:37:17 0 (published)
en14 English SlavicG 2022-07-24 12:35:10 46 Tiny change: 'in A$\n* $(A)$ — a set in brackets is a query\n* $k$ &m' -> 'in A$\n* $k$ &m'
en13 English SlavicG 2022-07-24 12:34:34 389
en12 English KrowSavcik 2022-07-24 12:29:11 253
en11 English SlavicG 2022-07-24 11:55:40 21 Tiny change: 's detailed.\n\n### ' -> 's detailed and not easy to find.\n\n### '
en10 English SlavicG 2022-07-24 11:54:53 4711 Tiny change: 'nd $1.85 \ cdot n / l' -> 'nd $1.85 \cdot n / l'
en9 English KrowSavcik 2022-07-24 11:07:59 258 Added gifs
en8 English KrowSavcik 2022-07-24 10:53:28 379 Tiny change: 'if)\n![ ](https://mirror.codeforces.com/2fca27/op2.gif)\n![ ](ht' -> 'if)\n![ ]()\n![ ](ht'
en7 English KrowSavcik 2022-07-24 08:57:55 1261 Tiny change: ' i)}$.\n\n' -> ' i)}$.\n\n* $v_{S[2 \cdot i + 1]} = v_{S_1[i]} + v_{S_2[i]}$\n\n'
en6 English SlavicG 2022-07-23 22:02:47 19
en5 English SlavicG 2022-07-23 21:20:21 1540 Tiny change: 'cdot f_k) \cap S_{k_2}[i' -> 'cdot f_k) / S_{k_2}[i'
en4 English SlavicG 2022-07-23 20:53:50 766 Tiny change: 'ated from $0$*\n\nAs it' -> 'ated from 0*\n\nAs it'
en3 English KrowSavcik 2022-07-23 20:17:23 783 Tiny change: 's $S_{k_1} \cup S_{k' -> 's $S_{k_1}[i] \cup S_{k'
en2 English KrowSavcik 2022-07-23 19:51:40 732 Tiny change: '.\n\n```\nq_i\n```\n\n' -> '.\n\n```\n$q_i$\n```\n\n'
en1 English SlavicG 2022-07-23 19:21:02 1001 Initial revision (saved to drafts)