Comment by 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