Fenwick Tree Pattern

When to use Fenwick Tree

• You need prefix sums (or range sums via subtraction) over an array that supports point updates.
• A pure prefix-sum array would force you to recompute O(n) entries on every mutation.
• The aggregate is invertible — sum, xor, or count — so range(l, r) = prefix(r) - prefix(l - 1).
• Memory is tight and the 4n footprint of a segment tree is undesirable.
• You are counting inversions, smaller-elements-to-the-right, or running rank queries on a compressed coordinate space.

Template

class FenwickTree {
  constructor(size) {
    this.n = size;
    this.tree = new Array(size + 1).fill(0);
  }
  update(index, delta) {
    let i = index + 1;
    while (i <= this.n) {
      this.tree[i] += delta;
      i += i & -i;
    }
  }
  prefixSum(index) {
    let i = index + 1;
    let sum = 0;
    while (i > 0) {
      sum += this.tree[i];
      i -= i & -i;
    }
    return sum;
  }
  rangeSum(left, right) {
    if (left === 0) return this.prefixSum(right);
    return this.prefixSum(right) - this.prefixSum(left - 1);
  }
  static fromArray(nums) {
    const bit = new FenwickTree(nums.length);
    for (let i = 0; i < nums.length; i++) {
      bit.tree[i + 1] += nums[i];
      const parent = (i + 1) + ((i + 1) & -(i + 1));
      if (parent <= nums.length) bit.tree[parent] += bit.tree[i + 1];
    }
    return bit;
  }
}

Common mistakes

• Mixing 0-indexed and 1-indexed conventions inside the tree, which makes the `i & -i` trick walk off the end or skip the root.
• Calling update(index, newValue) when the API actually takes a delta — you must compute delta = newValue - currentValue first, otherwise the tree drifts.
• Forgetting to size the array as n + 1 and indexing tree[0], which is reserved as a sentinel and must always remain zero.
• Using a Fenwick tree for range-min or range-max queries; the structure relies on invertibility and silently returns wrong answers for non-invertible aggregates.
• Building the tree with n separate update() calls when the linear-time bottom-up variant is available and trims a log factor off the construction.