A Fenwick tree supports point updates and prefix sums in O(log n) with just an array and some bit tricks: i & -i is the lowest set bit of i.
Implement a class Fenwick(n) over positions 0..n-1 (store a 1-based array internally):
add(i, delta): add delta at position iprefix_sum(i): the sum of positions 0..i-1 (so prefix_sum(0) == 0)range_sum(lo, hi): the sum over [lo, hi)Fenwick.from_list(values): build in O(n), not with n separate addslower_bound(target): for non-negative values, the smallest index i such that prefix_sum(i + 1) >= target, or n if none, in O(log n) by descending through powers of two