ID range searching In ld. the query is an interval First solution using ideas we know Interval trees Represent each point x by the interval [x,x Obtain a dynamic structure that can list k answers in a query in O(k Ig n) time c 2001 by erik D. Demaine Introduction to Ago orns Day 21 L12.6© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.6 1D range searching In 1D, the query is an interval: First solution using ideas we know: • Interval trees • Represent each point x by the interval [x, x]. • Obtain a dynamic structure that can list k answers in a query in O(k lg n) time