$\begingroup$
$\endgroup$
6
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.
Juho
22.9k7 gold badges63 silver badges118 bronze badges
asked Sep 18, 2014 at 8:57
-
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– Juho2014年09月18日 09:17:20 +00:00Commented Sep 18, 2014 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.– Issam T.2014年09月18日 09:20:40 +00:00Commented Sep 18, 2014 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– Juho2014年09月18日 09:21:36 +00:00Commented Sep 18, 2014 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.– Issam T.2014年09月18日 09:24:27 +00:00Commented Sep 18, 2014 at 9:24
-
2$\begingroup$ What is your space complexity constraint? $\endgroup$orezvani– orezvani2014年09月18日 09:25:59 +00:00Commented Sep 18, 2014 at 9:25
1 Answer 1
$\begingroup$
$\endgroup$
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.
answered Sep 18, 2014 at 9:31