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

Revision en1, by SlavicG, 2022-07-23 19:21:02

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.

The Idea

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://codeforces.me/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)