Data structure for counting bits set on a table

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.

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.

StackExchange Computer Science Q#30101, answer score: 2