Very clever but replacing O(1) with O(log n) for updates is probably worse than the benefit gained by O(log n) range-sum instead of O(n) when the updates are happening constantly, in real-time - think Twitter Firehose. In practice, it would make a lot more sense to pre-define the buckets and update those when doing insert/update/delete. Even 1m buckets is just 1-4MB of data, depending on how many counts do you want (2^8 - 2^32). That would give you O(1) update and O(k) range-sum where k = number of buckets. You want k to be smaller than n otherwise you're back to the naive implementation.
Fenwick trees were invented for context modeling with arithmetic coding. Reads and writes are perfectly balanced. For every symbol, there's one write to update the model and one read to determine the cumulative probability.
