Find an interval that overlaps 6-7. The tree is a BST on left endpoints, and each node shows its interval and, after the bar, the largest right endpoint anywhere in its subtree. That number is the whole trick: if the left subtree's max is below the query's low end, nothing on the left can overlap, so the search goes right without looking.
The code
Interval, kd and Range Trees, in Python
class Interval:
def __init__(self, lo, hi):
self.lo, self.hi = lo, hi
def overlap_search(n, q): # nodes keyed by lo, n.max = largest hi below
if n is None:
return None
if n.lo <= q.hi and q.lo <= n.hi: # found one
return n.interval
if n.left is not None and n.left.max >= q.lo: # something on the left can reach q
return overlap_search(n.left, q)
return overlap_search(n.right, q) # otherwise only the right side can
def kd_range(n, depth, r, out): # axis = depth % 2: 0 is x, 1 is y
if n is None:
return
if n.p in r:
out.append(n.p)
axis = depth % 2
v = n.p[axis]
if r.lo[axis] <= v: # the rectangle reaches the low side
kd_range(n.left, depth + 1, r, out)
if r.hi[axis] >= v: # and / or the high side
kd_range(n.right, depth + 1, r, out)
def range_query(root, x1, x2, y1, y2): # node.ys: subtree y values, sorted
split = root
while not split.leaf and (x2 < split.x or x1 > split.x):
split = split.left if x2 < split.x else split.right
count = 0
# walk down both sides from the split node; every subtree hanging off the path towards the
# range is canonical, and each is answered by a binary search in its sorted y list
for c in canonical_subtrees(split, x1, x2):
count += count_in_range(c.ys, y1, y2)
return count # O(log^2 n) with plain binary search
Interval, kd and Range Trees, in JavaScript
class Interval {
constructor(lo, hi) {
this.lo = lo;
this.hi = hi;
}
}
function overlapSearch(n, q) { // nodes keyed by lo, n.max = largest hi below
if (n === null) return null;
if (n.lo <= q.hi && q.lo <= n.hi) return n.interval; // found one
if (n.left !== null && n.left.max >= q.lo) return overlapSearch(n.left, q); // something on the left can reach q
return overlapSearch(n.right, q); // otherwise only the right side can
}
function kdRange(n, depth, r, out) { // axis = depth % 2: 0 is x, 1 is y
if (n === null) return;
if (r.contains(n.p)) out.push(n.p);
const axis = depth % 2;
const v = n.p[axis];
if (r.lo[axis] <= v) kdRange(n.left, depth + 1, r, out); // the rectangle reaches the low side
if (r.hi[axis] >= v) kdRange(n.right, depth + 1, r, out); // and / or the high side
}
function rangeQuery(root, x1, x2, y1, y2) { // node.ys: subtree y values, sorted
let split = root;
while (!split.leaf && (x2 < split.x || x1 > split.x)) split = x2 < split.x ? split.left : split.right;
let count = 0;
// walk down both sides from the split node; every subtree hanging off the path towards the
// range is canonical, and each is answered by a binary search in its sorted y list
for (const c of canonicalSubtrees(split, x1, x2)) count += countInRange(c.ys, y1, y2);
return count; // O(log^2 n) with plain binary search
}
Interval, kd and Range Trees, in Kotlin
class Interval(val lo: Int, val hi: Int)
fun overlapSearch(n: Node?, q: Interval): Interval? { // nodes keyed by lo, n.max = largest hi below
if (n == null) return null
if (n.lo <= q.hi && q.lo <= n.hi) return n.interval // found one
return if (n.left != null && n.left.max >= q.lo) overlapSearch(n.left, q) // something on the left can reach q
else overlapSearch(n.right, q) // otherwise only the right side can
}
fun kdRange(n: Node?, depth: Int, r: Rect, out: MutableList<Point>) { // axis = depth % 2: 0 is x, 1 is y
if (n == null) return
if (n.p in r) out += n.p
val axis = depth % 2; val v = n.p[axis]
if (r.lo[axis] <= v) kdRange(n.left, depth + 1, r, out) // the rectangle reaches the low side
if (r.hi[axis] >= v) kdRange(n.right, depth + 1, r, out) // and / or the high side
}
fun rangeQuery(root: Node, x1: Int, x2: Int, y1: Int, y2: Int): Int { // node.ys: subtree y values, sorted
var split = root
while (split.leaf == false && (x2 < split.x || x1 > split.x)) split = if (x2 < split.x) split.left else split.right
var count = 0
// walk down both sides from the split node; every subtree hanging off the path towards the
// range is canonical, and each is answered by a binary search in its sorted y list
for (c in canonicalSubtrees(split, x1, x2)) count += c.ys.countInRange(y1, y2)
return count // O(log^2 n) with plain binary search
}