0
$\begingroup$

I have a large array of bits of length $N$.
The query $f(k, m)$ means "find $kth$ zero in the array and the next $m-1$ zeros after it", $k \in [0, N-1], m \ll N$

Currently I use a segment tree over the bit array and my approaches were:

  • use kth zero search procedure $m$ times in $O(m \log{N})$
  • use the same kth zero search procedure but with divide-and-conquer approach:
    1. find the first $0th$ and the last $(m-1)th$ zero while also finding their LCA subtree
    2. find $(m/2)th$ zero in the LCA subtree
    3. recursively do 1. and 2. for both $0th$ and $(m / 2)th$ pair and $(m / 2)th$ and $(m-1)th$ pair
    this improves time greatly if the zeros are clustered but the worst time is still $O(m \log{N})$
  • maintain a link to the next zero for each member of the array, this gives $O(\log{N} + m)$ time but complicates array updates and requires additional $O(N)$ memory

I want any solution with better than $O(m \log{N})$ time.
I'm ready to switch to any other data structure if necessary.

Besides the aforementioned query the requirements are:

  • spatial complexity is $O(N)$
  • initialization in $O(N)$
  • update after a single bit in array is flipped in $O(logN)$
$\endgroup$
6
  • 2
    $\begingroup$ what operations does your data structure need? $\endgroup$
    – nir shahar
    Commented Dec 5, 2022 at 12:38
  • $\begingroup$ There are occasional updates of the bit array. The data stucture should be able to update itself after a single bit changed in $O(log N)$ or better. $\endgroup$ Commented Dec 5, 2022 at 13:53
  • $\begingroup$ Please don't respond with more information in the comments. Instead, edit your question so it reads well for someone who encounters it for the first time, and contains all necessary information, and so people don't need to read the comments to understand what you are asking. Thank you! I've provided similar feedback in the past: cs.stackexchange.com/questions/153435/#comment322876_153435, cs.stackexchange.com/questions/151051/#comment317584_151051 $\endgroup$
    – D.W.
    Commented Dec 5, 2022 at 19:17
  • $\begingroup$ @D.W. the question is updated $\endgroup$ Commented Dec 5, 2022 at 20:38
  • $\begingroup$ Do you allow allow adding links to the zeroes to organize them in a linked list ? $\endgroup$
    – user16034
    Commented Dec 8, 2022 at 14:58

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.