I personally enjoy the Fenwick Tree: https://en.m.wikipedia.org/wiki/Fenwick_tree https://en.m.wikipedia.org/wiki/Fenwick_tree What is it used for? It allows o

I personally enjoy the Fenwick Tree: https://en.m.wikipedia.org/wiki/Fenwick_tree https://en.m.wikipedia.org/wiki/Fenwick_tree What is it used for? It allows one to both query and update prefix sums in O(log n), for a normal array this would be O(n)/O(1) respectively. The cool thing is that it can be emulated with an array and as such it takes just the same amount of space as an array. The best part is that they can be implemented (simple version) in about 10 lines of C++ code.