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

Правка en1, от 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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский SlavicG 2022-07-29 12:41:24 8 Tiny change: '+ 2]} - c)$ & $1$\n\nThe ' -> '+ 2]} - c) \land 1$\n\nThe '
en17 Английский SlavicG 2022-07-29 12:40:12 12 Tiny change: 'that $c = S[0]$. We ' -> 'that $c = v_S[0]$. We '
en16 Английский KrowSavcik 2022-07-24 13:28:54 62 Minor correction
en15 Английский SlavicG 2022-07-24 12:37:17 0 (published)
en14 Английский 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 Английский SlavicG 2022-07-24 12:34:34 389
en12 Английский KrowSavcik 2022-07-24 12:29:11 253
en11 Английский SlavicG 2022-07-24 11:55:40 21 Tiny change: 's detailed.\n\n### ' -> 's detailed and not easy to find.\n\n### '
en10 Английский SlavicG 2022-07-24 11:54:53 4711 Tiny change: 'nd $1.85 \ cdot n / l' -> 'nd $1.85 \cdot n / l'
en9 Английский KrowSavcik 2022-07-24 11:07:59 258 Added gifs
en8 Английский 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 Английский 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 Английский SlavicG 2022-07-23 22:02:47 19
en5 Английский 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 Английский SlavicG 2022-07-23 20:53:50 766 Tiny change: 'ated from $0$*\n\nAs it' -> 'ated from 0*\n\nAs it'
en3 Английский 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 Английский 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 Английский SlavicG 2022-07-23 19:21:02 1001 Initial revision (saved to drafts)