Segment trees & Fenwick trees

Where the prefix-sum array falls over

A prefix-sum array is unbeatable on a static array: O(n) to build, O(1) per range query. The moment an element can change, it collapses — updating index i invalidates every prefix from i onward, so each update is O(n). Skip the precompute and you flip the problem: O(1) updates, O(n) queries. Either way an interleaved workload of q operations costs O(n·q), and with n and q around 10⁵ that's 10¹⁰ operations.

The move both structures make is the same one binary search makes: refuse to store either extreme. Don't store every individual element (queries too slow) and don't store every prefix (updates too slow) — store O(n) carefully chosen partial aggregates such that any range is assembled from O(log n) of them and any element belongs to only O(log n) of them.

The segment tree: one node per range

Build a binary tree over index ranges. The root covers [0, n−1], each internal node splits its range in half, and leaves are single elements. Every node caches the aggregate of its range. A query for [l, r] descends from the root and stops the instant a node's range is fully contained — so an arbitrary range is covered by at most 2 nodes per level, i.e. O(log n) nodes total.

Build, query, update

Store the tree in a flat array with the heap layout: node 1 is the root, node k's children are 2k and 2k+1. Every recursive call carries the range it owns (lo, hi) so no range metadata is stored per node.

class SegmentTree {
  constructor(nums) {
    this.n = nums.length;
    this.t = new Array(4 * this.n).fill(0); // 4n is the safe size — see the warning below
    if (this.n > 0) this._build(nums, 1, 0, this.n - 1);
  }

  _build(nums, node, lo, hi) {
    if (lo === hi) { this.t[node] = nums[lo]; return; } // leaf
    const mid = (lo + hi) >> 1;
    this._build(nums, 2 * node, lo, mid);
    this._build(nums, 2 * node + 1, mid + 1, hi);
    this.t[node] = this.t[2 * node] + this.t[2 * node + 1]; // merge children upward
  }

  // sum of nums[l..r] inclusive — O(log n)
  query(l, r, node = 1, lo = 0, hi = this.n - 1) {
    if (r < lo || hi < l) return 0;              // no overlap — return the IDENTITY, not 0 blindly
    if (l <= lo && hi <= r) return this.t[node]; // total overlap — cached answer, stop descending
    const mid = (lo + hi) >> 1;                  // partial overlap — split and combine
    return this.query(l, r, 2 * node, lo, mid)
         + this.query(l, r, 2 * node + 1, mid + 1, hi);
  }

  // set nums[i] = value — O(log n), touches exactly one root-to-leaf path
  update(i, value, node = 1, lo = 0, hi = this.n - 1) {
    if (lo === hi) { this.t[node] = value; return; }
    const mid = (lo + hi) >> 1;
    if (i <= mid) this.update(i, value, 2 * node, lo, mid);
    else          this.update(i, value, 2 * node + 1, mid + 1, hi);
    this.t[node] = this.t[2 * node] + this.t[2 * node + 1]; // re-merge on the way back up
  }
}

Range min, max, gcd — only the merge changes

Nothing about the traversal is sum-specific. Swap the merge function and the identity element and the same tree answers a different question. The only requirement is that the operation be associative — the tree combines sub-answers in a fixed nesting, so order of grouping must not matter.

That last column is the deep reason the two structures aren't interchangeable. A Fenwick tree answers range queries as prefix(r) − prefix(l−1), which needs an invertible operation. Min has no inverse — you cannot recover min(l..r) from min(0..r) and min(0..l−1) — so range-min genuinely requires a segment tree (or, if the array never changes, a sparse table).

Lazy propagation: range updates without touching every leaf

Now let updates be ranges too: "add 5 to everything in [l, r]." Doing that with point updates is O(n log n) per operation — worse than a plain loop. The fix is to be lazy: when a node's range is fully inside the update range, apply the change to that node's aggregate only and leave an IOU on it saying "my children still owe this." The IOU is pushed down one level at a time, and only when someone actually descends through that node.

The whole technique is two rules. Push before you look — any node you visit must settle its debt before you read or split it. Stop at total coverage — record the IOU and return without recursing. Together they keep every range update at O(log n).

class LazySumTree {
  constructor(n) {
    this.n = n;
    this.t = new Array(4 * n).fill(0);
    this.lazy = new Array(4 * n).fill(0); // pending "+x to every element in my range"
  }

  _push(node, lo, hi) {
    const add = this.lazy[node];
    if (add === 0) return;
    this.t[node] += add * (hi - lo + 1); // a range add of x raises the SUM by x * width
    if (lo !== hi) {                      // leaves have nobody to hand the debt to
      this.lazy[2 * node] += add;
      this.lazy[2 * node + 1] += add;
    }
    this.lazy[node] = 0;
  }

  rangeAdd(l, r, add, node = 1, lo = 0, hi = this.n - 1) {
    this._push(node, lo, hi);            // settle before doing anything else
    if (r < lo || hi < l) return;
    if (l <= lo && hi <= r) {            // fully covered — take the IOU and STOP
      this.lazy[node] += add;
      this._push(node, lo, hi);          // apply to this node so its parent can re-merge
      return;
    }
    const mid = (lo + hi) >> 1;
    this.rangeAdd(l, r, add, 2 * node, lo, mid);
    this.rangeAdd(l, r, add, 2 * node + 1, mid + 1, hi);
    this.t[node] = this.t[2 * node] + this.t[2 * node + 1];
  }

  query(l, r, node = 1, lo = 0, hi = this.n - 1) {
    this._push(node, lo, hi);            // same rule on the read path
    if (r < lo || hi < l) return 0;
    if (l <= lo && hi <= r) return this.t[node];
    const mid = (lo + hi) >> 1;
    return this.query(l, r, 2 * node, lo, mid)
         + this.query(l, r, 2 * node + 1, mid + 1, hi);
  }
}

Fenwick tree: the same job in a quarter of the code

A Binary Indexed Tree does point-update / prefix-query with one flat array and two three-line loops. The idea: store in t[k] the sum of the k & -k elements ending at k, where k & -k isolates the lowest set bit. Then any prefix is assembled by repeatedly stripping the lowest set bit, and any index is updated by repeatedly adding it — both take as many steps as there are bits, so O(log n).

class Fenwick {
  constructor(n) {
    this.n = n;
    this.t = new Array(n + 1).fill(0); // 1-INDEXED internally; index 0 is unusable
  }

  // add delta at 0-indexed position i — O(log n)
  update(i, delta) {
    for (let k = i + 1; k <= this.n; k += k & -k) this.t[k] += delta;
  }

  // sum of nums[0..i] inclusive — O(log n)
  prefix(i) {
    let sum = 0;
    for (let k = i + 1; k > 0; k -= k & -k) sum += this.t[k];
    return sum;
  }

  range(l, r) {
    return this.prefix(r) - (l > 0 ? this.prefix(l - 1) : 0); // needs an invertible op
  }

  // O(n) build — much better than n calls to update(), which is O(n log n)
  static from(nums) {
    const f = new Fenwick(nums.length);
    for (let i = 0; i < nums.length; i++) f.t[i + 1] += nums[i];
    for (let k = 1; k <= f.n; k++) {
      const parent = k + (k & -k);
      if (parent <= f.n) f.t[parent] += f.t[k]; // push each cell into the one that contains it
    }
    return f;
  }
}

Why Fenwick usually wins in practice

Both are O(log n), but the constants differ a lot. The Fenwick array is n+1 entries versus 4n; the loops are iterative with no recursion, no range bookkeeping and no branching; and access is a tight sequence of index arithmetic that the cache handles well. Expect a 2–4× real-time speedup and roughly a quarter of the code. It is also far easier to write correctly under interview pressure — two loops with no off-by-one range logic.

The price is expressiveness. Fenwick does point-update + prefix-query of an invertible operation, and (via a difference array) range-update + point-query. Everything else — range min/max, range update and range query together, "find the k-th element," storing anything richer than a number per node — is segment tree territory.

Count of smaller numbers after self — the classic BIT problem

For each element, how many elements to its right are strictly smaller? Brute force is O(n²). The trick is to sweep right-to-left over value ranks instead of positions: a Fenwick tree over ranks makes "how many already-seen values rank below this one?" a single prefix query.

// O(n log n) time, O(n) space
function countSmaller(nums) {
  // coordinate compression: values can be huge/negative, ranks are 0..m-1
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map(sorted.map((v, i) => [v, i]));

  const bit = new Fenwick(sorted.length);
  const res = new Array(nums.length);

  for (let i = nums.length - 1; i >= 0; i--) { // right to left: "seen" == "to my right"
    const r = rank.get(nums[i]);
    res[i] = r > 0 ? bit.prefix(r - 1) : 0; // count of seen values with a STRICTLY lower rank
    bit.update(r, 1);                        // now this element counts as seen
  }
  return res;
}

Coordinate compression is the reusable half of this idea: whenever you want a Fenwick indexed by value but values are unbounded, sort the distinct values and index by rank. The same right-to-left + BIT skeleton solves counting inversions, "reverse pairs," and range-sum-count problems — recognising the skeleton is worth more than memorising any one of them.

Which one to reach for

Recognizing it in an unseen problem

• Queries and updates are interleaved over the same array — that single word "update" is what rules out a prefix-sum array
• Constraints around n, q ≥ 10⁵ with per-query work implied — O(n·q) is 10¹⁰, so an O(log n) per operation structure is the intended answer
• Brute force is "recompute the range every time"; the fix is caching O(n) partial aggregates so any range is O(log n) of them
• Sum-like and invertible (sum, XOR, count) → Fenwick. Min/max/gcd, or updates that span ranges → segment tree
• "How many earlier/later elements are smaller/larger" or "count inversions" → sweep in one direction with a Fenwick over compressed value ranks, not over positions
• Distinguish from a heap: a heap gives you the global min/max with updates, but cannot answer a specific range. Distinguish from a sorted structure: if you need order statistics plus ranges, that's a Fenwick over ranks
• If the array never changes after construction, stop — prefix sums or a sparse table, and say why you didn't build a tree