[gordaco]

Fenwick Trees (which, despite the name, are implemented using an array) allow counting prefix sums AND updating prefix sums in O(log n) time. Very useful when n is in the order of millions. I have used them a few times in Project Euler problems.

https://en.wikipedia.org/wiki/Fenwick_tree

[almog]

Was going to mention Fenwick Tree here as well, but since you've already did, I'll just add that this is IMO a great introduction to Fenwick Trees: https://www.youtube.com/watch?v=kPaJfAUwViY

[nyanpasu64]

Is it possible to implement a Fenwick tree using a tree, and support quickly adding and removing items as well as quickly shifting the positions of suffixes?

[pjscott]

Yes! This is both possible and fairly easy.

[kragen]

Yes.

[EnderShadow8]

Segment trees are objectively superior in all ways except implementation length

[almog]

Another advantage to Fenwick Tree: while it shares asymptotic space complexity with Segment Tree, it has better constant factors, which can be useful in very restricted environments.

[silverlake]

I used fenwick trees in a smart contract because space/time costs money.