Fenwick Tree
A short, fast structure for prefix sums with updates, built on the lowest set bit of an index, also used for counting and range add.
The problem
You have an array of n numbers. An operation either changes one element or asks for the sum of a prefix a[1..i]. You can already do this with a segment tree. A Fenwick tree (also called a binary indexed tree, BIT) does the same job in about ten lines and runs faster.
1 of 9