title: How to efficiently find a contiguous range of used/free slots from a Fenwick tree
body: <p>Assume, that I am tracking the usage of slots in a Fenwick tree. As an example, lets consider tracking 32 slots, leading to a Fenwick tree layout as shown in the image below, where the numbers in the grid indicate the index in the underlying array with counts manipulated by the Fenwick tree where the value in each cell is the sum of "used" items in that segment (i.e. array cell 23 stores the amount of used slots in the range [16-23]). The items at the lowest level (i.e. cells 0, 2, 4, ...) can only have the value of "1" (used slot) or "0" (free slot). </p>
  
  <p><img src="https://i.stack.imgur.com/wVK2B.png" alt="Example Fenwick tree layout"></p>
  
  <p>What I am looking for is an efficient algorithm to find the first range of a given number of contiguous free slots.</p>
  
  <p>To illustrate, suppose I have the Fenwick tree shown in the image below in which a total of 9 slots are used (note that the light gray numbers are just added for clarity, not actually stored in the tree's array cells).</p>
  
  <p><img src="https://i.stack.imgur.com/INdUe.png" alt="Example tree"></p>
  
  <p>Now I would like to find e.g. the first contiguous range of 10 free slots, which should find this range:</p>
  
  <p><img src="https://i.stack.imgur.com/MrwIB.png" alt="Example search result"></p>
  
  <p>I can't seem to find an efficient way of doing this, and it is giving me a bit of a headache. Note, that as the required amount of storage space is critical for my purposes, I do not wish to extend the design to be a segment tree. </p>
  
  <p>Any thoughts and suggestions on an O(log N) type of solution would be very welcome.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>Time for an update after bounty period has expired. Thanks for all comments, questions, suggestions and answers. They have made me think things over again, taught me a lot and pointed out to me (once again; one day I may learn this lesson) that I should focus more on the issue I want to solve when asking questions. </p>
  
  <p>Since <a href="https://stackoverflow.com/users/337475/erik-p" title="@Erik P.">@Erik P</a> was the only one that provided a reasonable answer to the question <em>that included the requested code/pseudo code</em>, he will receive the bounty. </p>
  
  <p>He also pointed out correctly that O(log N) search using this structure is not going to be possible. Kudos to <a href="https://stackoverflow.com/users/2825668/dan-bjorge" title="@DanBjorge">@DanBjorge</a> for providing a proof that made me think about worst case performance. </p>
  
  <p>The comment and answer of <a href="https://stackoverflow.com/users/1009831/evgeny-kluev" title="@EvgenyKluev">@EvgenyKluev</a> made me realize I should have formulated my question differently. In fact I was already doing in large part what he suggested (see <a href="https://gist.github.com/anonymous/7594508" rel="nofollow noreferrer">https://gist.github.com/anonymous/7594508</a> - which shows where I got stuck before posting this question), and asked this question hoping there would be an efficient way to search contiguous ranges, thereby preventing changing this design to a segment tree (which would require an additional 1024 bytes). It appears however that such a change might be the smart thing to do.</p>
  
  <p>For anyone interested, a binary encoded Fenwick tree matching the example used in this question (32 slot fenwick tree encoded in 64 bits) can be found here: <a href="https://gist.github.com/anonymous/7594245" rel="nofollow noreferrer">https://gist.github.com/anonymous/7594245</a>.</p>