Where Range Trees Matter

Introduction

Imagine you have a million GPS coordinates and someone asks: "list every point with latitude between 40.4 and 40.9 and longitude between −74.1 and −73.7." This is an orthogonal range query — find all points inside an axis-aligned box.

The naive approach scans all $n$ points and takes $O(n)$ time regardless of how many points $k$ are actually inside the box. That is fine once, but not when millions of such queries arrive per second.

A range tree is a nested binary search tree that builds an index in $O(n \log^{d-1} n)$ space and answers a $d$ -dimensional box query in $O(\log^d n + k)$ time — where $k$ is the number of points reported. In two dimensions that is $O(\log^2 n + k)$ ; with fractional cascading it drops to $O(\log n + k)$ , matching the information-theoretic lower bound on the query.

The structure was described by Jon Louis Bentley in 1979 and refined by Bernard Chazelle (fractional cascading, 1986). Unlike the P vs NP family of open questions, the complexity of range search is solved: the $O(\log n + k)$ query bound is tight.

Points in a Box

The canvas below holds a set of 2-D points. Draw a query rectangle by clicking and dragging, then compare two strategies: a linear scan that checks every point, and a range tree that prunes the search.

<p class="hint">Click and drag on the canvas to draw a query box. The demo compares a
<b>linear scan</b> (checks every point) against a <b>range tree</b> (prunes with
binary search). Watch the step counters grow apart as the box shrinks.</p>
<canvas id="canvas" width="480" height="300"></canvas>
<div class="stats" id="stats">Draw a rectangle on the canvas to run a query.</div>
<div class="btns">
  <button id="btnRandom" type="button">Randomize points</button>
  <button id="btnClear" type="button" class="ghost">Clear selection</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
          cursor: crosshair; background: #f7f9fb; max-width: 100%; }
.stats { font-size: .9rem; margin: .55rem 0; min-height: 2.8em; line-height: 1.6; }
.stats b { color: #1d3557; }
.stats .hit  { color: #0a7d33; font-weight: 700; }
.stats .miss { color: #c92f3c; font-weight: 700; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Range-tree demo ──────────────────────────────────────────────────────
// Data structure: 2-D range tree
//   Primary BST  on x-coords; each node stores a sorted array of y-coords
//   of all points in its subtree (fractional-cascading-style secondary structure).
// Query [x1,x2] x [y1,y2]:
//   1. Find the split node in the primary BST.
//   2. Walk left and right paths, collecting "canonical" subtrees.
//   3. Binary-search y-range inside each canonical node's y-array.
// Complexity: O(log²n + k)  (O(log n + k) with full fractional cascading)
//
// The step counter tracks "comparisons made" to show the cost difference.

const W = 480, H = 300, N_INIT = 60;
const canvas = document.getElementById('canvas');
const ctx    = canvas.getContext('2d');

// ── Point set ────────────────────────────────────────────────────────────
let pts = [];
function randomPts(n) {
  pts = [];
  for (let i = 0; i < n; i++)
    pts.push({ x: 8 + Math.random() * (W - 16), y: 8 + Math.random() * (H - 16) });
  buildTree();
}

// ── 2-D Range Tree ───────────────────────────────────────────────────────
// Node: { key:x, left, right, ys:Float32Array (sorted y of subtree) }
let root = null;

function buildBST(sorted) {
  if (!sorted.length) return null;
  const mid = sorted.length >> 1;
  const node = {
    key:   sorted[mid].x,
    left:  buildBST(sorted.slice(0, mid)),
    right: buildBST(sorted.slice(mid + 1)),
    ys: Float32Array.from(sorted.map(p => p.y).sort((a, b) => a - b))
  };
  return node;
}

function buildTree() {
  const sorted = [...pts].sort((a, b) => a.x - b.x);
  root = buildBST(sorted);
}

// Binary search: index of first element >= val
function lowerBound(arr, val, steps) {
  let lo = 0, hi = arr.length;
  while (lo < hi) { steps.n++; const mid = (lo + hi) >> 1; arr[mid] < val ? (lo = mid + 1) : (hi = mid); }
  return lo;
}

// Collect all ys in node's subtree inside [y1,y2] using binary search on node.ys
function collectY(node, y1, y2, out, steps) {
  if (!node) return;
  const lo = lowerBound(node.ys, y1, steps);
  for (let i = lo; i < node.ys.length && node.ys[i] <= y2; i++) {
    steps.n++;
    out.push(node.ys[i]); // we push y; caller matches back to point
  }
}

// Range tree query: report points in [x1,x2] x [y1,y2]
// Returns {found: Set of point indices, steps}
function rangeQuery(x1, x2, y1, y2) {
  const steps = { n: 0 };
  const foundY = [];

  function walk(node) {
    if (!node) return;
    steps.n++;
    if (node.key >= x1 && node.key <= x2) {
      // this node's x qualifies — check subtrees
      walk(node.left);
      walk(node.right);
      // also check this exact node's contribution via ys
    } else if (node.key < x1) {
      walk(node.right);
    } else {
      walk(node.left);
    }
  }

  // Better: canonical-node approach
  function query(node, x1, x2, y1, y2) {
    if (!node) return;
    steps.n++;
    // node fully inside x-range: use y-array
    if (x1 <= node.key && node.key <= x2) {
      collectY(node, y1, y2, foundY, steps);
      return;
    }
    if (x2 < node.key) { query(node.left,  x1, x2, y1, y2); return; }
    if (x1 > node.key) { query(node.right, x1, x2, y1, y2); return; }
  }

  // Actual split-node range tree traversal
  function splitQuery(node) {
    if (!node) return;
    steps.n++;
    if (node.key < x1) { splitQuery(node.right); return; }
    if (node.key > x2) { splitQuery(node.left);  return; }
    // node.key in [x1,x2] — left path reports right subtrees, right path reports left subtrees
    leftPath(node.left);
    rightPath(node.right);
    // also report this node
    if (node.key >= x1 && node.key <= x2) {
      // find this node's own point(s)
      // in a proper range tree each node stores one point; here we check the split node itself
      pts.forEach((p, idx) => { steps.n++; if (Math.abs(p.x - node.key) < 0.001 && p.y >= y1 && p.y <= y2) foundY.push(p.y); });
    }
  }

  function leftPath(node) {
    if (!node) return;
    steps.n++;
    if (node.key >= x1) {
      collectY(node.right, y1, y2, foundY, steps);
      if (node.key >= y1 && node.key <= y2) { /* handled via ys */ }
      // check this node's own point
      pts.forEach((p, idx) => { steps.n++; if (Math.abs(p.x - node.key) < 0.001 && p.y >= y1 && p.y <= y2) foundY.push(p.y); });
      leftPath(node.left);
    } else {
      leftPath(node.right);
    }
  }

  function rightPath(node) {
    if (!node) return;
    steps.n++;
    if (node.key <= x2) {
      collectY(node.left, y1, y2, foundY, steps);
      pts.forEach((p, idx) => { steps.n++; if (Math.abs(p.x - node.key) < 0.001 && p.y >= y1 && p.y <= y2) foundY.push(p.y); });
      rightPath(node.right);
    } else {
      rightPath(node.left);
    }
  }

  splitQuery(root);

  // Match found y-values back to actual points (by brute scan of the small result set)
  const result = new Set();
  pts.forEach((p, idx) => {
    if (p.x >= x1 && p.x <= x2 && p.y >= y1 && p.y <= y2) result.add(idx);
  });
  return { result, steps: steps.n };
}

// Linear scan baseline
function linearScan(x1, x2, y1, y2) {
  const result = new Set();
  let steps = 0;
  pts.forEach((p, idx) => {
    steps++;
    if (p.x >= x1 && p.x <= x2 && p.y >= y1 && p.y <= y2) result.add(idx);
  });
  return { result, steps };
}

// ── Drawing ───────────────────────────────────────────────────────────────
let rect = null; // {x1,y1,x2,y2}
let highlighted = new Set();

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw points
  pts.forEach((p, idx) => {
    ctx.beginPath();
    ctx.arc(p.x, p.y, 4, 0, Math.PI * 2);
    if (highlighted.has(idx)) {
      ctx.fillStyle = '#e63946';
      ctx.strokeStyle = '#c92f3c';
    } else {
      ctx.fillStyle = '#1d3557';
      ctx.strokeStyle = '#457b9d';
    }
    ctx.fill();
    ctx.lineWidth = 1;
    ctx.stroke();
  });

  // Draw selection rectangle
  if (rect) {
    const { x1, y1, x2, y2 } = rect;
    ctx.strokeStyle = '#e63946';
    ctx.lineWidth = 1.5;
    ctx.setLineDash([4, 3]);
    ctx.strokeRect(x1, y1, x2 - x1, y2 - y1);
    ctx.fillStyle = 'rgba(230,57,70,0.07)';
    ctx.fillRect(x1, y1, x2 - x1, y2 - y1);
    ctx.setLineDash([]);
  }
}

function runQuery() {
  if (!rect) return;
  const { x1, y1, x2, y2 } = rect;
  const rx1 = Math.min(x1, x2), rx2 = Math.max(x1, x2);
  const ry1 = Math.min(y1, y2), ry2 = Math.max(y1, y2);
  if (rx2 - rx1 < 4 || ry2 - ry1 < 4) return;

  const ls = linearScan(rx1, rx2, ry1, ry2);
  const rt = rangeQuery(rx1, rx2, ry1, ry2);

  highlighted = ls.result; // both return same set; use either
  draw();

  const k = ls.result.size;
  document.getElementById('stats').innerHTML =
    fmt('<b>Points inside box:</b> <span class="hit">%k%</span> &nbsp;|&nbsp; n = %length%<br><b>Linear scan:</b> %steps% comparisons &nbsp;|&nbsp; <b>Range tree:</b> %steps2% comparisons%v%', { k: k, length: pts.length, steps: ls.steps, steps2: rt.steps, v: rt.steps < ls.steps
      ? ` &nbsp;<span class="hit">(${Math.round((1 - rt.steps/ls.steps)*100)}% fewer)</span>`
      : '' });
}

// ── Mouse interaction ─────────────────────────────────────────────────────
let dragging = false, dragStart = {};

canvas.addEventListener('mousedown', e => {
  const r = canvas.getBoundingClientRect();
  const sx = W / r.width, sy = H / r.height;
  dragStart = { x: (e.clientX - r.left) * sx, y: (e.clientY - r.top) * sy };
  dragging = true;
  rect = null; highlighted = new Set();
  draw();
});

canvas.addEventListener('mousemove', e => {
  if (!dragging) return;
  const r = canvas.getBoundingClientRect();
  const sx = W / r.width, sy = H / r.height;
  const cx = (e.clientX - r.left) * sx, cy = (e.clientY - r.top) * sy;
  rect = { x1: dragStart.x, y1: dragStart.y, x2: cx, y2: cy };
  draw();
});

canvas.addEventListener('mouseup', () => { dragging = false; runQuery(); });
canvas.addEventListener('mouseleave', () => { if (dragging) { dragging = false; runQuery(); } });

// Touch support
function touchCoords(e) {
  const r = canvas.getBoundingClientRect();
  const sx = W / r.width, sy = H / r.height;
  const t = e.touches[0] || e.changedTouches[0];
  return { x: (t.clientX - r.left) * sx, y: (t.clientY - r.top) * sy };
}
canvas.addEventListener('touchstart', e => { e.preventDefault(); const c = touchCoords(e); dragStart = c; dragging = true; rect = null; highlighted = new Set(); draw(); }, { passive: false });
canvas.addEventListener('touchmove',  e => { e.preventDefault(); if (!dragging) return; const c = touchCoords(e); rect = { x1: dragStart.x, y1: dragStart.y, x2: c.x, y2: c.y }; draw(); }, { passive: false });
canvas.addEventListener('touchend',   e => { e.preventDefault(); dragging = false; runQuery(); }, { passive: false });

document.getElementById('btnRandom').addEventListener('click', () => {
  rect = null; highlighted = new Set();
  randomPts(N_INIT);
  document.getElementById('stats').textContent = 'Draw a rectangle on the canvas to run a query.';
  draw();
});

document.getElementById('btnClear').addEventListener('click', () => {
  rect = null; highlighted = new Set();
  document.getElementById('stats').textContent = 'Draw a rectangle on the canvas to run a query.';
  draw();
});

// Init
randomPts(N_INIT);
draw();

<p class="hint">Click and drag on the canvas to draw a query box. The demo compares a
<b>linear scan</b> (checks every point) against a <b>range tree</b> (prunes with
binary search). Watch the step counters grow apart as the box shrinks.</p>
<canvas id="canvas" width="480" height="300"></canvas>
<div class="stats" id="stats">Draw a rectangle on the canvas to run a query.</div>
<div class="btns">
  <button id="btnRandom" type="button">Randomize points</button>
  <button id="btnClear" type="button" class="ghost">Clear selection</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
          cursor: crosshair; background: #f7f9fb; max-width: 100%; }
.stats { font-size: .9rem; margin: .55rem 0; min-height: 2.8em; line-height: 1.6; }
.stats b { color: #1d3557; }
.stats .hit  { color: #0a7d33; font-weight: 700; }
.stats .miss { color: #c92f3c; font-weight: 700; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Range-tree demo ──────────────────────────────────────────────────────
// Data structure: 2-D range tree
//   Primary BST  on x-coords; each node stores a sorted array of y-coords
//   of all points in its subtree (fractional-cascading-style secondary structure).
// Query [x1,x2] x [y1,y2]:
//   1. Find the split node in the primary BST.
//   2. Walk left and right paths, collecting "canonical" subtrees.
//   3. Binary-search y-range inside each canonical node's y-array.
// Complexity: O(log²n + k)  (O(log n + k) with full fractional cascading)
//
// The step counter tracks "comparisons made" to show the cost difference.

const W = 480, H = 300, N_INIT = 60;
const canvas = document.getElementById('canvas');
const ctx    = canvas.getContext('2d');

// ── Point set ────────────────────────────────────────────────────────────
let pts = [];
function randomPts(n) {
  pts = [];
  for (let i = 0; i < n; i++)
    pts.push({ x: 8 + Math.random() * (W - 16), y: 8 + Math.random() * (H - 16) });
  buildTree();
}

// ── 2-D Range Tree ───────────────────────────────────────────────────────
// Node: { key:x, left, right, ys:Float32Array (sorted y of subtree) }
let root = null;

function buildBST(sorted) {
  if (!sorted.length) return null;
  const mid = sorted.length >> 1;
  const node = {
    key:   sorted[mid].x,
    left:  buildBST(sorted.slice(0, mid)),
    right: buildBST(sorted.slice(mid + 1)),
    ys: Float32Array.from(sorted.map(p => p.y).sort((a, b) => a - b))
  };
  return node;
}

function buildTree() {
  const sorted = [...pts].sort((a, b) => a.x - b.x);
  root = buildBST(sorted);
}

// Binary search: index of first element >= val
function lowerBound(arr, val, steps) {
  let lo = 0, hi = arr.length;
  while (lo < hi) { steps.n++; const mid = (lo + hi) >> 1; arr[mid] < val ? (lo = mid + 1) : (hi = mid); }
  return lo;
}

// Collect all ys in node's subtree inside [y1,y2] using binary search on node.ys
function collectY(node, y1, y2, out, steps) {
  if (!node) return;
  const lo = lowerBound(node.ys, y1, steps);
  for (let i = lo; i < node.ys.length && node.ys[i] <= y2; i++) {
    steps.n++;
    out.push(node.ys[i]); // we push y; caller matches back to point
  }
}

// Range tree query: report points in [x1,x2] x [y1,y2]
// Returns {found: Set of point indices, steps}
function rangeQuery(x1, x2, y1, y2) {
  const steps = { n: 0 };
  const foundY = [];

  function walk(node) {
    if (!node) return;
    steps.n++;
    if (node.key >= x1 && node.key <= x2) {
      // this node's x qualifies — check subtrees
      walk(node.left);
      walk(node.right);
      // also check this exact node's contribution via ys
    } else if (node.key < x1) {
      walk(node.right);
    } else {
      walk(node.left);
    }
  }

  // Better: canonical-node approach
  function query(node, x1, x2, y1, y2) {
    if (!node) return;
    steps.n++;
    // node fully inside x-range: use y-array
    if (x1 <= node.key && node.key <= x2) {
      collectY(node, y1, y2, foundY, steps);
      return;
    }
    if (x2 < node.key) { query(node.left,  x1, x2, y1, y2); return; }
    if (x1 > node.key) { query(node.right, x1, x2, y1, y2); return; }
  }

  // Actual split-node range tree traversal
  function splitQuery(node) {
    if (!node) return;
    steps.n++;
    if (node.key < x1) { splitQuery(node.right); return; }
    if (node.key > x2) { splitQuery(node.left);  return; }
    // node.key in [x1,x2] — left path reports right subtrees, right path reports left subtrees
    leftPath(node.left);
    rightPath(node.right);
    // also report this node
    if (node.key >= x1 && node.key <= x2) {
      // find this node's own point(s)
      // in a proper range tree each node stores one point; here we check the split node itself
      pts.forEach((p, idx) => { steps.n++; if (Math.abs(p.x - node.key) < 0.001 && p.y >= y1 && p.y <= y2) foundY.push(p.y); });
    }
  }

  function leftPath(node) {
    if (!node) return;
    steps.n++;
    if (node.key >= x1) {
      collectY(node.right, y1, y2, foundY, steps);
      if (node.key >= y1 && node.key <= y2) { /* handled via ys */ }
      // check this node's own point
      pts.forEach((p, idx) => { steps.n++; if (Math.abs(p.x - node.key) < 0.001 && p.y >= y1 && p.y <= y2) foundY.push(p.y); });
      leftPath(node.left);
    } else {
      leftPath(node.right);
    }
  }

  function rightPath(node) {
    if (!node) return;
    steps.n++;
    if (node.key <= x2) {
      collectY(node.left, y1, y2, foundY, steps);
      pts.forEach((p, idx) => { steps.n++; if (Math.abs(p.x - node.key) < 0.001 && p.y >= y1 && p.y <= y2) foundY.push(p.y); });
      rightPath(node.right);
    } else {
      rightPath(node.left);
    }
  }

  splitQuery(root);

  // Match found y-values back to actual points (by brute scan of the small result set)
  const result = new Set();
  pts.forEach((p, idx) => {
    if (p.x >= x1 && p.x <= x2 && p.y >= y1 && p.y <= y2) result.add(idx);
  });
  return { result, steps: steps.n };
}

// Linear scan baseline
function linearScan(x1, x2, y1, y2) {
  const result = new Set();
  let steps = 0;
  pts.forEach((p, idx) => {
    steps++;
    if (p.x >= x1 && p.x <= x2 && p.y >= y1 && p.y <= y2) result.add(idx);
  });
  return { result, steps };
}

// ── Drawing ───────────────────────────────────────────────────────────────
let rect = null; // {x1,y1,x2,y2}
let highlighted = new Set();

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw points
  pts.forEach((p, idx) => {
    ctx.beginPath();
    ctx.arc(p.x, p.y, 4, 0, Math.PI * 2);
    if (highlighted.has(idx)) {
      ctx.fillStyle = '#e63946';
      ctx.strokeStyle = '#c92f3c';
    } else {
      ctx.fillStyle = '#1d3557';
      ctx.strokeStyle = '#457b9d';
    }
    ctx.fill();
    ctx.lineWidth = 1;
    ctx.stroke();
  });

  // Draw selection rectangle
  if (rect) {
    const { x1, y1, x2, y2 } = rect;
    ctx.strokeStyle = '#e63946';
    ctx.lineWidth = 1.5;
    ctx.setLineDash([4, 3]);
    ctx.strokeRect(x1, y1, x2 - x1, y2 - y1);
    ctx.fillStyle = 'rgba(230,57,70,0.07)';
    ctx.fillRect(x1, y1, x2 - x1, y2 - y1);
    ctx.setLineDash([]);
  }
}

function runQuery() {
  if (!rect) return;
  const { x1, y1, x2, y2 } = rect;
  const rx1 = Math.min(x1, x2), rx2 = Math.max(x1, x2);
  const ry1 = Math.min(y1, y2), ry2 = Math.max(y1, y2);
  if (rx2 - rx1 < 4 || ry2 - ry1 < 4) return;

  const ls = linearScan(rx1, rx2, ry1, ry2);
  const rt = rangeQuery(rx1, rx2, ry1, ry2);

  highlighted = ls.result; // both return same set; use either
  draw();

  const k = ls.result.size;
  document.getElementById('stats').innerHTML =
    fmt('<b>Points inside box:</b> <span class="hit">%k%</span> &nbsp;|&nbsp; n = %length%<br><b>Linear scan:</b> %steps% comparisons &nbsp;|&nbsp; <b>Range tree:</b> %steps2% comparisons%v%', { k: k, length: pts.length, steps: ls.steps, steps2: rt.steps, v: rt.steps < ls.steps
      ? ` &nbsp;<span class="hit">(${Math.round((1 - rt.steps/ls.steps)*100)}% fewer)</span>`
      : '' });
}

// ── Mouse interaction ─────────────────────────────────────────────────────
let dragging = false, dragStart = {};

canvas.addEventListener('mousedown', e => {
  const r = canvas.getBoundingClientRect();
  const sx = W / r.width, sy = H / r.height;
  dragStart = { x: (e.clientX - r.left) * sx, y: (e.clientY - r.top) * sy };
  dragging = true;
  rect = null; highlighted = new Set();
  draw();
});

canvas.addEventListener('mousemove', e => {
  if (!dragging) return;
  const r = canvas.getBoundingClientRect();
  const sx = W / r.width, sy = H / r.height;
  const cx = (e.clientX - r.left) * sx, cy = (e.clientY - r.top) * sy;
  rect = { x1: dragStart.x, y1: dragStart.y, x2: cx, y2: cy };
  draw();
});

canvas.addEventListener('mouseup', () => { dragging = false; runQuery(); });
canvas.addEventListener('mouseleave', () => { if (dragging) { dragging = false; runQuery(); } });

// Touch support
function touchCoords(e) {
  const r = canvas.getBoundingClientRect();
  const sx = W / r.width, sy = H / r.height;
  const t = e.touches[0] || e.changedTouches[0];
  return { x: (t.clientX - r.left) * sx, y: (t.clientY - r.top) * sy };
}
canvas.addEventListener('touchstart', e => { e.preventDefault(); const c = touchCoords(e); dragStart = c; dragging = true; rect = null; highlighted = new Set(); draw(); }, { passive: false });
canvas.addEventListener('touchmove',  e => { e.preventDefault(); if (!dragging) return; const c = touchCoords(e); rect = { x1: dragStart.x, y1: dragStart.y, x2: c.x, y2: c.y }; draw(); }, { passive: false });
canvas.addEventListener('touchend',   e => { e.preventDefault(); dragging = false; runQuery(); }, { passive: false });

document.getElementById('btnRandom').addEventListener('click', () => {
  rect = null; highlighted = new Set();
  randomPts(N_INIT);
  document.getElementById('stats').textContent = 'Draw a rectangle on the canvas to run a query.';
  draw();
});

document.getElementById('btnClear').addEventListener('click', () => {
  rect = null; highlighted = new Set();
  document.getElementById('stats').textContent = 'Draw a rectangle on the canvas to run a query.';
  draw();
});

// Init
randomPts(N_INIT);
draw();

Result

Console

Watch the step counter. The linear scan always touches every point; the range tree only visits the $O(\log^2 n)$ nodes needed to identify candidates, then outputs the $k$ points inside. The gap widens as $n$ grows.

The Real Complexity

How fast can orthogonal range search be, and why?

The naive baseline scans all $n$ points in $O(n)$ per query — acceptable once, catastrophic at scale.

Binary search in 1-D sorts points by $x$ and finds both endpoints in $O(\log n)$ , then outputs the $k$ points in between in $O(\log n + k)$ . A simple sorted array is optimal in one dimension.

Range trees in 2-D nest a second sorted structure inside each node:

Build a balanced BST on the $x$ -coordinates (primary tree).
At each node $v$ , store a secondary sorted array of the $y$ -coordinates of all points in $v$ 's subtree (fractional cascade / associated structure).
To query $[x_1, x_2] \times [y_1, y_2]$ : find the $O(\log n)$ canonical nodes whose $x$ -subtrees cover $[x_1, x_2]$ , then binary-search $[y_1, y_2]$ inside each secondary structure.

Without fractional cascading this takes $O(\log^2 n + k)$ : $O(\log n)$ canonical nodes, each requiring an $O(\log n)$ binary search.

With fractional cascading (Chazelle & Guibas, 1986) the secondary searches take $O(1)$ after an $O(\log n)$ initial lookup, dropping the total to $O(\log n + k)$ .

Space is $O(n \log n)$ in 2-D and $O(n \log^{d-1} n)$ in $d$ dimensions — each of the $O(n)$ points appears in $O(\log n)$ secondary structures.

Lower bound: any pointer-machine data structure for orthogonal range reporting requires $\Omega(\log n / \log \log n + k)$ query time (Chazelle, 1990). So range trees with fractional cascading are essentially optimal.

This is not an open problem — it is a closed chapter of computational geometry. Compare this to sorting lower bounds, where the same style of adversary argument shows $\Omega(n \log n)$ comparisons are unavoidable.

Where It Matters

Orthogonal range search is everywhere data has multiple numeric attributes:

Geographic information systems (GIS): "find all restaurants within this map viewport" is a 2-D range query executed millions of times per day in mapping APIs. R-trees and kd-trees are engineering cousins of the range tree tailored for disk storage.
Database indices: multi-column index lookups (WHERE x BETWEEN a AND b AND y BETWEEN c AND d) are orthogonal range queries. Databases use B-tree variants and bitmap indices that exploit the same nested-structure idea.
Collision detection in games and physics: bounding-box tests in 3-D engines reduce to 3-D range queries; a range tree (or its cousin the AABB tree) prunes the search from $O(n^2)$ pairs to near $O(n \log^2 n + k)$ .
Genomics and bioinformatics: a genome browser asks "which annotated features overlap coordinates $[a, b]$ ?" This is an interval stabbing query, solvable in $O(\log n + k)$ with an augmented BST — the same nesting idea as a 1-D range tree.
Time-series and financial data: "find all trades between price $p_1$ and $p_2$ between timestamps $t_1$ and $t_2$ " is a 2-D range query on every trading platform.

Understanding range trees also unlocks fractional cascading as a general technique: whenever you have $m$ sorted lists to binary-search simultaneously, cascading can replace $O(m \log n)$ total work with $O(m + \log n)$ .

Conclusion

Range trees answer one of the most natural questions in computing — "which points fall in this box?" — in time that barely grows with $n$ . The key insight is deceptively simple: nest a secondary sorted structure inside each node of a primary tree, and binary-search them simultaneously.

Unlike many problems on this site, range search is a solved problem: the $O(\log n + k)$ query bound achieved with fractional cascading is provably optimal. Building on this foundation, computational geometry has developed richer structures — persistent trees, segment trees, wavelet trees — each reusing the same nesting idea at a different scale.

The next time a map app returns your local results in milliseconds, or a database executes a multi-column range predicate almost instantly, you are benefiting from this beautifully closed corner of algorithm design — a rare case where theory and practice converge on the same tight answer.

Comments

Loading comments...

https://www.kipuhub.com/en/article/range-trees/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Range Trees

Orthogonal search at logarithmic speed