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.