Segment Tree / BIT

How to think about it

A prefix sum answers range sums in O(1) - but if a value changes, every prefix after it must be recomputed in O(n). A Fenwick tree (BIT) fixes this by storing partial sums in a clever array where index i stores the sum of a range of length lowbit(i). Update: add to every ancestor index. Query: sum every ancestor prefix. Both are O(log n) via bit tricks.

A segment tree generalizes to non-invertible operations (min, max, count). It is a binary tree over the array: each node stores the aggregate of its range. Leaves are elements; internal nodes merge two children. Point update walks down one root-to-leaf path; range query descends only into overlapping nodes. For range updates (add v to every element in [l, r]), add lazy propagation: defer child updates until a query touches them.

Template shapes

Shape	Core move	Example
BIT (point update, range sum)	update(i, +v), query(r), query(l-1)	LC 307
Segment tree (range min/max)	Build, point update, merge on query	LC 315
Lazy propagation (range add)	Push lazy tag on descend, pull on return	LC 1649
2D segment tree	Tree of trees over rows × cols	LC 308

Complexity baseline

Build: O(n) (or O(n log n) naive). Update: O(log n). Query: O(log n). Space: O(n) for BIT, O(4n) for segment tree (safe array size). Lazy propagation adds O(1) per node visited.

From template to problem

1. Decide: is the operation invertible (sum, xor) → BIT? Or non-invertible (min, max) → segment tree?
2. Use 1-indexed internally for BIT (update(i+1)); segment tree can be 0-indexed.
3. For range updates, implement lazy propagation or use a BIT with difference-array trick.
4. If queries are static (no updates), a plain prefix sum is simpler and faster.

/**
 * Segment Tree / BIT template.
 * This skeleton implements a Fenwick tree (BIT) for point-update range-sum.
 * A segment tree handles the same range queries plus non-invertible operations
 * (min, max, count); see the guide for the tree structure.
 */

export class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}

/**
 * Segment Tree / BIT template.
 * This skeleton implements a Fenwick tree (BIT) for point-update range-sum.
 * A segment tree handles the same range queries plus non-invertible operations
 * (min, max, count); see the guide for the tree structure.
 */

export class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}