Fenwick tree (binary indexed tree)

In short: A Fenwick tree stores an array of numbers so that both updating a value and computing prefix sums take O(log n).

In more detail: It is a particularly compact alternative to the segment tree when only sums (or similar invertible operations) are needed. The tree lives in a plain array, and the index arithmetic uses the lowest set bit.

In Depth

• Idea: Position i stores the sum of a section whose length equals the largest power of two dividing i.
• Query: Prefix sum up to i: add the value, then i -= i & -i until i is 0.
• Update: Change a value by d: add at i, then i += i & -i until i exceeds the size.
• Range sum: sum(r) - sum(l-1).
• Build: Possible in O(n), memory only n numbers.
• Limits: Not every operation is invertible. A range minimum therefore usually needs the segment tree.

See also: Big-O notation