The trick

Sort queries by (left / sqrt(N), then right). Move current [L, R] pointers to each query's range. Total movement O((N+Q) × sqrt(N)).

Advertisement

Implementation sketch

Arrays.sort(queries, (a, b) -> {
  int bA = a.l / block, bB = b.l / block;
  if (bA != bB) return bA - bB;
  return a.r - b.r;
});
int curL = 0, curR = -1, curAns = 0;
for (Query q : queries) {
  while (curR < q.r) add(++curR);
  while (curL > q.l) add(--curL);
  while (curR > q.r) remove(curR--);
  while (curL < q.l) remove(curL++);
  q.ans = curAns;
}
Advertisement

When it wins

Complex queries (mode, distinct count) that don't fit segment tree.

Offline only

Requires all queries upfront. Online queries need segment tree or other DS.