ID range searching In ld. the query is an interval Second solution using ideas we know Sort the points and store them in an array Solve query by binary search on endpoints Obtain a static structure that can list k answers in a query in O(k + Ig n)time Goal: obtain a dynamic structure that can list k answers in a query in O(k+lg n)time c 2001 by erik D. Demaine Introduction to Agorithms Day 21 L12.7© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.7 1D range searching In 1D, the query is an interval: Second solution using ideas we know: • Sort the points and store them in an array • Solve query by binary search on endpoints. • Obtain a static structure that can list k answers in a query in O(k + lg n) time. Goal: Obtain a dynamic structure that can list k answers in a query in O(k + lg n) time