1
$\begingroup$

I am trying to understand how a sparse table can be used as a prefix sum data structure for a bit vector. In the screendump below 1 the article [2] very vaguely describes how to use a sparse table from article "Storing a sparse table" to do this is $O(1)$ with space: $O(k\cdot loglogn)$. For simplicity, we can assume that $k=n/logn$. How is this even possible? and what is $|z_i|=n^{O(1)}$?

prosition from article

Article [2]: https://dl.acm.org/doi/abs/10.1137/S0097539700369909

Article [16]: https://dl.acm.org/doi/10.1145/359168.359175

Improve this question
$\endgroup$
4
  • $\begingroup$ Please provide a proper citation for all copied material, and for the paper [16]. We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$ Commented May 9, 2021 at 7:26
  • $\begingroup$ What's unclear about the proof in the paper? $n^O(1)$ is a short hand for $O(n^c)$ for some constant $c$. $\endgroup$ Commented May 9, 2021 at 23:25
  • $\begingroup$ It is unclear that $|z_i|$ has a size of $O(n^c)$. What does it mean? Also, how can the max function yield a $logn^{O(1)}$ when $|z_i|$ can clearly end as the result of max? $\endgroup$ Commented May 10, 2021 at 6:25
  • $\begingroup$ $|z_i| \in O(n^c)$ by hypothesis, so there is nothing to prove there (the $|\cdot|$ symbol just means "absolute value"). I think that the $\max$ in the statement should probably be $\min$ (the proof for the claim as written is formally correct, but the claim forces all $|z_i|$ to be in $O(\log^c n)$, which makes the condition $|z_i| \in O(n^c)$ redundant). The proof works as-is when $\max$ is replaced with $\min$. $\endgroup$ Commented May 10, 2021 at 12:19

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.