Fenwick Trees: Point Update, Prefix Sum

Prefix sums answer range sums on a static array. The moment you need a[i] += d and then another range sum, the prefix is stale and rebuilding is O(n) per update. At n, q ≤ 2·10⁵ that is dead.

A Fenwick tree (BIT) keeps the same prefix identity, but each index i stores the sum of a responsibility range ending at i. The length of that range is the lowest set bit of i.

CSES Dynamic Range Sum Queries is the drill. USACO Gold 'More on Prefix Sums / BIT' is the module. 1-based indexing is the contest convention — tree[0] is unused.

1-based Fenwick, point add + prefix sumjs

function createFenwick(n) {
  const bit = Array(n + 1).fill(0);
  function add(i, delta) {
    for (; i <= n; i += i & -i) bit[i] += delta;
  }
  function prefix(i) {
    let s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
  }
  function range(l, r) {
    return prefix(r) - prefix(l - 1);
  }
  return { add, prefix, range };
}

TRACE

n = 8. add(3, 5), then prefix(4). Which tree cells change?

i = 3

3 in binary is 0011. lowest bit = 1. bit[3] += 5. Next i = 3+1 = 4.

bit[3] += 5

1 / 4

CHECK

range sum [l, r] on a Fenwick is prefix(r) - prefix(l-1). What is prefix(0)?

WA modes:

- 0-based input, 1-based tree. add(i, d) with i = 0 infinite-loops (i += i & -i stays 0). Always add(i+1, d). - Overflow. Same as prefixes: long long. - **Point *set*, not add. To set `a[i] = v`, add `v - current`. Keep the raw array beside the tree, or query the point first. - Using Fenwick for range-add + point-query is the difference-array trick on the tree (add at l, subtract at r+1). Range-add + range-sum needs two Fenwicks or a segment tree. - Min instead of sum.** Fenwick needs an invertible operation. Min is not invertible — use a segment tree.

CHECK

n, q = 2·10⁵. Mix of point adds and range sums. Why not a segment tree?

Checks 0/2

Next lesson