Fenwick Trees

Binary Indexed Trees: prefix sums with point updates in $O(\log n)$ using low-bit tricks.

Advanced

Shorter than segment trees when you only need prefix sums.

def add(i, v):
    while i <= n: bit[i] += v; i += i & -i
def prefix(i):
    s = 0
    while i > 0: s += bit[i]; i -= i & -i
    return s

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)