Fenwick Tree (Binary Indexed Tree)

A Fenwick tree — also called a Binary Indexed Tree, or BIT — is a compact array structure that answers prefix-sum queries and applies point updates in O(log n) time each. It solves the problem where a plain prefix-sum array makes queries instant but every update O(n), and a plain array makes updates instant but every query O(n); the Fenwick tree keeps both logarithmic, with far less code and memory than a segment tree for the sum case. It does this with one trick — the lowest set bit of an index, x & -x — which you will build up in the solution. Your fenwickTree(arr) factory takes a numeric array and returns an object with update, prefixSum, and rangeSum. See Fenwick tree for background.

Signature

function fenwickTree(arr: number[]): {
  update(i: number, delta: number): void;  // ADD delta to the element at index i
  prefixSum(i: number): number;            // sum of arr[0..i] inclusive
  rangeSum(l: number, r: number): number;  // sum of arr[l..r] inclusive
};

Examples

const ft = fenwickTree([1, 3, 5, 7, 9, 11]);
ft.prefixSum(0);   // 1    — just arr[0]
ft.prefixSum(2);   // 9    — 1 + 3 + 5
ft.rangeSum(1, 3); // 15   — 3 + 5 + 7
ft.rangeSum(0, 5); // 36   — the whole array

const ft = fenwickTree([1, 3, 5, 7, 9, 11]);
ft.update(2, 5);   // element 2 goes 5 -> 10 (adds 5, does not replace)
ft.prefixSum(2);   // 14   — 1 + 3 + 10
ft.rangeSum(0, 5); // 41   — now 36 + 5
ft.rangeSum(2, 2); // 10   — the updated element on its own

Notes

• Caller indices are 0-based — arr is indexed from 0 the way you would expect. Internally the tree is 1-based, but that is your implementation detail; the caller never sees it.
• update adds a delta — it does not set a value. To change arr[i] to some newVal, first work out the delta yourself: update(i, newVal - current).
• Ranges are inclusive — prefixSum(i) includes index i; rangeSum(l, r) includes both l and r. Assume 0 <= l <= r <= n - 1.
• Both queries and updates are O(log n) — a for loop that re-sums the array on every query, or rebuilds prefixes on every update, is the thing this structure exists to beat.
• Do not mutate the input — read arr to build your tree, but leave the caller's array untouched.