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.
Data structure for counting bits set on a table
algorithms;data structures;trees
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.