I have a table that contains only bits. I would like to be able to do the following two queries:

  • SET any bit to 0 or 1;
  • GET the number of bits that are set to 1 from the beginning of the table up to a specifique index i.

Is there a data structure that is more efficient than a binary indexed tree, i.e. a Fenwick tree? A binary indexed tree performs both operations in $O(\log n)$ time, where $n$ is the number of elements.

For practical info, my tables are really large, containing up to millions of elements.

  • 1
    $\begingroup$ For a practical implementation, one could experiment with a bitvector, or maybe a (dynamic) array of say 64-bit words. There are very fast bit counting methods available, see e.g. SSE4 popcnt. Of course theoretically, the GET operation requires linear time. Real performance will however depend on size of $n$. $\endgroup$ – Juho Sep 18 '14 at 9:17
  • $\begingroup$ @Juho, I am not sure you can play with the index i using popcnt. I will add a precision in the Question a precision about n $\endgroup$ – Issam T. Sep 18 '14 at 9:20
  • 1
    $\begingroup$ Not directly. Depending on what $i$ is, you can first popcount enough words, and then start counting bits one-by-one when you hit the right word, if you see what I mean. And also, if you want, you can increase the bit level parallelism by counting in parallel with AVX2 vector registers. $\endgroup$ – Juho Sep 18 '14 at 9:21
  • $\begingroup$ Yes I understood what you mean. But this won't be good for a small $n$ as the number of words will be small. And it won't be efficient of large $n$ since it will only add a factor of 1/64 in front of the linear complexity. However it may be a solution for medium range tables... $\endgroup$ – Issam T. Sep 18 '14 at 9:24
  • 2
    $\begingroup$ What is your space complexity constraint? $\endgroup$ – orezvani Sep 18 '14 at 9:25

If one of the operations is much more common, you could use an array of bits resp. of counts, so the common operation can be done in $O(1)$ at the cost of the other operation taking $O(n)$.

If you can't make such an assumption, then I don't think there is anything better than the $O(\log n)$ of the BIT.


Your Answer

