Data Structureshard

What is a Fenwick tree (Binary Indexed Tree) used for?

Answer

A Fenwick tree supports prefix sums and point updates in O(log n) with O(n) memory. Use it when you need many updates and queries like “sum of [0..i]” quickly (e.g., frequency/counting problems).

class Fenwick {
  private bit: number[];

  constructor(n: number) {
    this.bit = Array(n + 1).fill(0);
  }

  add(i: number, delta: number) {
    for (let x = i + 1; x < this.bit.length; x += x & -x) this.bit[x] += delta;
  }

  sum(i: number) {
    let res = 0;
    for (let x = i + 1; x > 0; x -= x & -x) res += this.bit[x];
    return res;
  }
}

Advanced answer

Deep dive

Expanding on the short answer — what usually matters in practice:

Context (tags): fenwick, bit, prefix-sum, big-o
Complexity: compare typical operations (average vs worst-case).
Invariants: what must always hold for correctness.
When the choice is wrong: production symptoms (latency, GC, cache misses).
Explain the "why", not just the "what" (intuition + consequences).
Trade-offs: what you gain/lose (time, memory, complexity, risk).
Edge cases: empty inputs, large inputs, invalid inputs, concurrency.

Examples

Here’s an additional example (building on the short answer):

class Fenwick {
  private bit: number[];

  constructor(n: number) {
    this.bit = Array(n + 1).fill(0);
  }

  add(i: number, delta: number) {
    for (let x = i + 1; x < this.bit.length; x += x & -x) this.bit[x] += delta;
  }

  sum(i: number) {
    let res = 0;
    for (let x = i + 1; x > 0; x -= x & -x) res += this.bit[x];
    return res;
  }
}

Common pitfalls

Too generic: no concrete trade-offs or examples.
Mixing average-case and worst-case (e.g., complexity).
Ignoring constraints: memory, concurrency, network/disk costs.

Interview follow-ups

When would you choose an alternative and why?