Segment Tree / Fenwick

A tree over ranges where each node stores an aggregate, giving logarithmic queries and updates.

AdvancedO(log n) per query and updateNew5 problems

mastery

Trigger phrases

If a problem statement sounds like one of these, try this pattern first.

range query with updates

count of smaller numbers after self

range minimum

The template

Get this into muscle memory, then adapt the condition per problem.

function update(node: number, l: number, r: number, i: number, v: number) {
  if (l === r) { tree[node] = v; return; }
  const m = (l + r) >> 1;
  i <= m ? update(2*node, l, m, i, v) : update(2*node+1, m+1, r, i, v);
  tree[node] = tree[2*node] + tree[2*node+1];
}