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
  }
}

Dry run: query(2,5), then update(4,10), then query(2,5) again — on [3,1,4,1,5,9,2,6]

Only the nodes on the root-to-leaf chain for index 4 ever change — 12, then 6, then 3, then 1 — which is exactly why update is O(log n) instead of O(n). The first query(2,5) never even visits node 12; it reads the already-cached t[6] = 14. The update then refreshed that cache to 19 on its way up, so bumping index 4 from 5 to 10 shifts the range answer from 19 to 24 without anyone re-summing the range.

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).

Struct nodes: when a node stores more than one number

So far every node held one number and the merge was one operator. Some questions need a node to remember several facts about its range, so that two halves can be combined without re-reading either. The standard example is the maximum subarray sum (the best non-empty contiguous run) with point updates, which a Fenwick tree cannot do and a prefix-sum array cannot do once values change.

Ask what you would need to know about a left half L and a right half R to get the answer for the joined range. The best subarray of L∪R is one of three things: entirely inside L, entirely inside R, or crossing the middle, in which case it is a suffix of L glued to a prefix of R. So each node stores four numbers: sum (the whole range), prefix (the best run starting at the left end), suffix (the best run ending at the right end) and best (the best run anywhere). Each of the four can itself be derived from the children's four:

class MaxSubarrayTree {
  constructor(nums) {
    this.n = nums.length;
    this.t = new Array(4 * this.n);
    if (this.n > 0) this._build(nums, 1, 0, this.n - 1);
  }

  static leaf(v) { return { sum: v, prefix: v, suffix: v, best: v }; } // non-empty runs only

  static merge(a, b) { // order matters: a is the LEFT half
    return {
      sum: a.sum + b.sum,
      prefix: Math.max(a.prefix, a.sum + b.prefix),
      suffix: Math.max(b.suffix, b.sum + a.suffix),
      best: Math.max(a.best, b.best, a.suffix + b.prefix),
    };
  }

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

  update(i, value, node = 1, lo = 0, hi = this.n - 1) {
    if (lo === hi) { this.t[node] = MaxSubarrayTree.leaf(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] = MaxSubarrayTree.merge(this.t[2 * node], this.t[2 * node + 1]);
  }

  // best subarray sum inside nums[l..r] — O(log n)
  query(l, r, node = 1, lo = 0, hi = this.n - 1) {
    if (r < lo || hi < l) return null; // no zero-like identity exists, so "nothing" is null
    if (l <= lo && hi <= r) return this.t[node];
    const mid = (lo + hi) >> 1;
    const left = this.query(l, r, 2 * node, lo, mid);
    const right = this.query(l, r, 2 * node + 1, mid + 1, hi);
    if (left === null) return right;
    if (right === null) return left;
    return MaxSubarrayTree.merge(left, right);
  }

  best(l, r) { return this.query(l, r).best; }
}

Dry run: build on [1, −3, 4, 2], then set index 1 to 5

The cost per query and per update is still O(log n); only the constant grows, because a node is four numbers and a merge is a handful of operations. The principle is the useful part: when a question about a range cannot be answered from one number per half, add the facts that can, until the merge closes. Longest run of equal values, the number of runs, "is this range sorted" and range-gcd-with-count are all built this way.

The iterative bottom-up segment tree

The recursive tree needs 4n cells and pays for a function call per level. When you can use the half-open convention, there is a much shorter version with a flat array of exactly 2n cells: leaf i lives at index n + i, and node k is the merge of nodes 2k and 2k+1. Building is a single backwards loop, updating is "write the leaf, then walk to the root", and a query walks inward from both ends of the range at once.

class BottomUpTree {
  constructor(nums, merge, identity) {
    this.n = nums.length;
    this.merge = merge;
    this.identity = identity;
    this.t = new Array(2 * this.n).fill(identity);
    for (let i = 0; i < this.n; i++) this.t[this.n + i] = nums[i]; // leaves
    for (let k = this.n - 1; k >= 1; k--) this.t[k] = merge(this.t[2 * k], this.t[2 * k + 1]);
  }

  update(i, value) {
    let k = i + this.n;
    this.t[k] = value;
    for (k >>= 1; k >= 1; k >>= 1) this.t[k] = this.merge(this.t[2 * k], this.t[2 * k + 1]);
  }

  // merge of nums[l..r-1], half-open — O(log n)
  query(l, r) {
    let left = this.identity, right = this.identity;
    for (l += this.n, r += this.n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) left = this.merge(left, this.t[l++]);     // l is a right child: take it, step past it
      if (r & 1) right = this.merge(this.t[--r], right);   // r is exclusive: step back, then take it
    }
    return this.merge(left, right);
  }
}

Here is why the loop works. At each level, l is the leftmost node whose range is still inside the query, and r is one past the rightmost. If l is odd it is a right child, so its parent would also cover an element left of the query: take l alone and move one step right. If r is odd then r - 1 is a left child whose parent would cover an element right of the query: take r - 1 alone. Then both indices halve and the same argument holds one level up. Each level takes at most two nodes, so a query is O(log n).

Dry run: query(2, 6) on [3, 1, 4, 1, 5, 9, 2, 6] with sum

The answer 19 matches the recursive tree's query(2, 5) from the dry run above, and it took two reads. Note the half-open range: the second argument is one past the last index.

Use this version when you want the smallest, fastest code for point update and range query. Its limits: lazy propagation is awkward without the recursive structure, and the "descend by comparing the children" idiom in the next section is easier on the recursive layout.

Descending the tree: the leftmost index at or above a threshold

A segment tree can also answer questions about positions, not just ranges. Take an array of capacities and the request "find the leftmost bin with capacity at least x, then use some of it." Scanning is O(n). If each node stores the maximum of its range, you can decide in O(1) whether a range contains any bin with capacity ≥ x, and descend straight to the answer: go left if the left child's maximum is enough, otherwise go right.

class MaxTree {
  constructor(nums) {
    this.n = nums.length;
    this.t = new Array(4 * this.n).fill(-Infinity);
    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; }
    const mid = (lo + hi) >> 1;
    this._build(nums, 2 * node, lo, mid);
    this._build(nums, 2 * node + 1, mid + 1, hi);
    this.t[node] = Math.max(this.t[2 * node], this.t[2 * node + 1]);
  }

  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] = Math.max(this.t[2 * node], this.t[2 * node + 1]);
  }

  // smallest index i >= from with nums[i] >= x, or -1 — O(log n)
  firstAtLeast(x, from = 0, node = 1, lo = 0, hi = this.n - 1) {
    if (hi < from || this.t[node] < x) return -1; // out of range, or no bin here is big enough
    if (lo === hi) return lo;
    const mid = (lo + hi) >> 1;
    const found = this.firstAtLeast(x, from, 2 * node, lo, mid);
    return found !== -1 ? found : this.firstAtLeast(x, from, 2 * node + 1, mid + 1, hi);
  }
}

Without the from argument the search is one root-to-leaf walk: at every node, the left child either has a bin that fits (go there; the answer is the leftmost one) or it does not and the right child must. With from some nodes straddle the start position, but a straddling node exists at only one position per level, and any node fully to the right of from is either rejected in O(1) by its maximum or contains the answer, so the total is still O(log n). Dry run on [5, 3, 9, 2, 7, 8, 1, 6]:

The same shape answers "leftmost position whose prefix sum reaches k" (store sums, compare against the remaining amount while descending) and, with a min tree, "first index whose value is at most x". Whenever a loop over positions asks for the first one that satisfies a monotone test on a range aggregate, descend instead.

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);
  }
}

My Calendar III: a dynamic tree and tags that never move

A booking [start, end) arrives, and after each one you must report the largest number of bookings that overlap at any single moment. Times go up to 10⁹, so an array indexed by time is impossible, and bookings arrive online, so you cannot compress coordinates in advance. This is a range-add, global-max problem, which is exactly what a segment tree with lazy updates does, if the tree is built on demand.

Two ideas combine. First, a dynamic tree: nodes are objects created only when an update descends into them, so the tree over [0, 10⁹] has about log₂(10⁹) ≈ 30 levels but only O(log C) new nodes per booking. Second, tags that never move. In the earlier lazy tree you pushed a pending add down to the children before looking at them. For "add to a range, ask for the maximum" there is a simpler trick: leave the tag on the node where the update stopped, and let every ancestor recompute its maximum as its own tag + the larger child maximum. Nothing is ever pushed down, so no node ever needs to be visited just to settle a debt.

class MyCalendarThree {
  constructor() {
    this.root = this._node();
  }

  _node() { return { max: 0, add: 0, left: null, right: null }; }

  // book [startTime, endTime) and return the largest overlap so far — O(log C) per call
  book(startTime, endTime) {
    this._add(this.root, 0, 1000000000, startTime, endTime - 1); // closed [l, r] inside the tree
    return this.root.max;
  }

  _add(node, lo, hi, l, r) {
    if (r < lo || hi < l) return;
    if (l <= lo && hi <= r) { // fully covered: tag this node and stop
      node.max++;
      node.add++;
      return;
    }
    const mid = Math.floor((lo + hi) / 2);
    if (node.left === null) node.left = this._node();
    if (node.right === null) node.right = this._node();
    this._add(node.left, lo, mid, l, r);
    this._add(node.right, mid + 1, hi, l, r);
    node.max = node.add + Math.max(node.left.max, node.right.max); // the tag still applies to everything below
  }
}

The invariant is that node.max is the largest overlap anywhere in the node's range, counting the tags on the node itself and below it but not on its ancestors. When a booking fully covers a node, every point in it gains one booking, so both the maximum and the stored tag go up by one. A parent re-derives its maximum from its children's maxima plus its own tag. The root has no ancestors, so root.max is the global answer.

Memory is about O(n log C) nodes for n bookings, because each booking creates at most a few nodes per level. When all the bookings are known in advance, an even simpler method sweeps sorted start and end events and counts, but the online version above is the one that survives a follow-up of "what if they arrive one at a time?"

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 (a two-tree trick exists for sums, but the segment tree is the general tool), 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.

Fenwick binary descent: the k-th element in O(log n)

Suppose a Fenwick tree holds counts, so prefix(i) is how many items have a value at index ≤ i. A natural question is the reverse one: "what is the smallest index whose prefix count reaches k?", which is the k-th smallest item of a multiset that supports insert and delete. Binary searching over prefix works but costs O(log² n): a log for the search and a log for each prefix. The Fenwick layout lets you do it in one O(log n) walk.

Recall that t[k] covers the block of k & -k items ending at k. Start at position 0 and try to move right by the biggest power of two, then the next biggest, and so on. A jump of step from pos lands on pos + step, and because pos only has bits larger than step set, the cell t[pos + step] covers exactly the step items just after pos. So you can ask "would taking this whole block still leave the prefix below the target?" and decide each bit of the answer from the high end, exactly as in a binary search over bits.

// smallest 0-indexed i with prefix(i) >= target, or f.n if the total is smaller.
// Every entry must be >= 0 so that prefix sums never decrease. O(log n).
function lowerBound(f, target) {
  let top = 1;
  while (top * 2 <= f.n) top *= 2; // the largest power of two that fits

  let pos = 0, remaining = target;
  for (let step = top; step > 0; step >>= 1) {
    if (pos + step <= f.n && f.t[pos + step] < remaining) {
      pos += step;               // the whole block is still too small: jump over it
      remaining -= f.t[pos];
    }
  }
  return pos; // pos items have a prefix below target, so the answer is item number pos (0-indexed)
}

Dry run: values 1 to 8 live at indices 0 to 7, with counts [1, 0, 2, 0, 1, 0, 0, 3], so the multiset is 1, 3, 3, 5, 8, 8, 8 and the 4th smallest should be 5, which is index 4. The Fenwick cells are t[4] = 1+0+2+0 = 3, t[6] = 1+0 = 1, t[5] = 1 and t[8] = 7.

This is the engine behind "k-th smallest in a dynamic multiset", "find the person at position k after removals" (keep a 1 per present person, delete by subtracting 1) and "k-th missing number" style questions. It only works on a Fenwick tree built over counts; the segment tree does the same thing by descending with the left child's total, and handles more kinds of nodes.

Range add and range sum with two Fenwick trees

The earlier table says a Fenwick tree over a difference array supports range update with a point query. To get range updates and range sums you can use a segment tree with lazy tags, or you can pay two Fenwick trees and a little algebra. Derive it, because the formula is easy to forget but easy to rebuild.

Let d[j] be the difference array, d[j] = a[j] - a[j-1] (with a[-1] = 0), so a[k] is the sum of d[0..k]. A range add of x on [l, r] changes just two entries: d[l] += x and d[r+1] -= x. The prefix sum of a up to i is

S(i) = Σ_k≤i a[k] = Σ_k≤i Σ_j≤k d[j] = Σ_j≤i d[j] · (i − j + 1) = (i + 1) · Σ_j≤i d[j] − Σ_j≤i j · d[j]

The middle step counts how many times each d[j] is included: once for each k from j to i, which is i − j + 1 times. The last form needs only two prefix sums: one over d[j] and one over j · d[j]. Keep one Fenwick tree for each.

class RangeFenwick {
  constructor(n) {
    this.n = n;
    this.byD = new Fenwick(n);     // prefix sums of d[j]
    this.byJD = new Fenwick(n);    // prefix sums of j * d[j]
  }

  _addAt(j, x) { // d[j] += x
    this.byD.update(j, x);
    this.byJD.update(j, x * j);
  }

  // add x to every element in [l, r] — O(log n)
  rangeAdd(l, r, x) {
    this._addAt(l, x);
    if (r + 1 < this.n) this._addAt(r + 1, -x); // nothing to cancel past the end
  }

  _prefix(i) {
    if (i < 0) return 0;
    return (i + 1) * this.byD.prefix(i) - this.byJD.prefix(i);
  }

  // sum of a[l..r] — O(log n)
  rangeSum(l, r) {
    return this._prefix(r) - this._prefix(l - 1);
  }
}

This reuses the Fenwick class from earlier in the chapter. Dry run on five zeros: rangeAdd(1, 3, 5) sets d[1] = 5 and d[4] = −5, so the stored arrays are:

Now rangeSum(0, 2) is S(2) − S(−1) with S(2) = 3 · (0 + 5 + 0) − (0 + 5 + 0) = 10, which is a[0] + a[1] + a[2] = 0 + 5 + 5. And S(4) = 5 · (0 + 5 + 0 + 0 − 5) − (0 + 5 + 0 + 0 − 20) = 0 + 15 = 15, which is 5 + 5 + 5 over the whole array. Each call is four Fenwick operations, O(log n), with no recursion and no tags to push.

Offline sort plus Fenwick: reverse pairs and range-sum counts

The count-of-smaller sweep generalises. Whenever a question is "for each element, count the earlier (or later) elements that stand in some order relation to it", sweep in index order, keep a Fenwick tree indexed by compressed value, and for each element ask for a range of values among the elements already inserted. Two questions show the pattern with a twist: the value you compare against is not the element itself.

Reverse pairs: count i < j with nums[i] > 2 · nums[j]

For each j, the number of earlier elements larger than 2·nums[j] is "how many have I inserted" minus "how many inserted are at most 2·nums[j]". The value 2·nums[j] need not be in the array, so find its position among the sorted distinct values with a binary search for how many values are ≤ it.

// number of entries in the ascending array sorted that are <= x
function countAtMost(sorted, x) {
  let lo = 0, hi = sorted.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (sorted[mid] <= x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// number of entries in the ascending array sorted that are < x
function countLess(sorted, x) {
  let lo = 0, hi = sorted.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (sorted[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// O(n log n) time, O(n) space
function reversePairs(nums) {
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  const bit = new Fenwick(sorted.length);
  let pairs = 0;
  for (let j = 0; j < nums.length; j++) {
    const upTo = countAtMost(sorted, 2 * nums[j]);         // ranks 0..upTo-1 are values <= 2 * nums[j]
    const notBigger = upTo > 0 ? bit.prefix(upTo - 1) : 0; // inserted values that are NOT bigger
    pairs += j - notBigger;                                 // j values were inserted so far
    bit.update(countLess(sorted, nums[j]), 1);              // the rank of nums[j] is how many values are below it
  }
  return pairs;
}

On [1, 3, 2, 3, 1] the sorted distinct values are 1, 2, 3 with ranks 0, 1, 2. The answer should be 2, from the pairs (index 1, index 4) and (index 3, index 4), since 3 > 2·1:

At j = 4 the inserted values are 1, 3, 2, 3. Those at most 2 are 1 and 2, so two are not bigger, and 4 − 2 = 2 are bigger: the two 3s.

Count of range sum: how many subarrays have a sum in [lower, upper]

Let P be the prefix sums with P[0] = 0. A subarray ending at j and starting after i has sum P[j] − P[i], so you need the number of earlier prefix values P[i] in the window [P[j] − upper, P[j] − lower]. That is a range query on the Fenwick tree over compressed prefix values, the difference of two prefix counts.

// O(n log n) time, O(n) space; needs countAtMost and countLess from above
function countRangeSum(nums, lower, upper) {
  const prefix = [0];
  for (const x of nums) prefix.push(prefix[prefix.length - 1] + x);

  const sorted = [...new Set(prefix)].sort((a, b) => a - b);
  const bit = new Fenwick(sorted.length);
  let total = 0;
  for (const p of prefix) {
    const from = countLess(sorted, p - upper);   // ranks below this are too small
    const to = countAtMost(sorted, p - lower);   // ranks below this hold values at most p - lower
    const atMost = to > 0 ? bit.prefix(to - 1) : 0;
    const below = from > 0 ? bit.prefix(from - 1) : 0;
    total += atMost - below;
    bit.update(countLess(sorted, p), 1);         // insert AFTER counting, so only earlier prefixes are matched
  }
  return total;
}

On nums = [−2, 5, −1] with the window [−2, 2], the prefix sums are [0, −2, 3, 2] and the answer is 3 (the subarrays [−2], [−2, 5, −1] and [−1]):

The reusable skeleton is: (1) turn the question into "for each j, count earlier i whose value falls in a window that depends on j"; (2) compress the values you will insert; (3) sweep, query the window as the difference of two prefix counts, then insert. Merge sort can solve the same two problems in the same time, but the Fenwick version is shorter to write once the helper exists, and each element is counted the moment it is inserted (the values still have to be known up front for the compression).

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
• The answer for a range cannot be built from one number per half (best subarray, longest run, is-it-sorted) → a segment tree whose node stores a small struct, merged left-to-right
• "Find the first / leftmost / k-th position such that ..." with updates → descend a tree of aggregates (maxima in a segment tree, counts in a Fenwick) instead of scanning
• "Count pairs i < j with a relation between nums[i] and a transform of nums[j]" → sweep j, query a window of ranks among the inserted values, then insert
• Range add and range sum with a tight code budget → two Fenwick trees; times up to 10⁹ arriving online → a dynamic segment tree