线段树

Segment trees and interval trees Lecture 5 Antoine Vigneron antoine.vigneron@jouy.inra.fr INRA Lecture 5:Segment trees and interval trees – p.1/37 Outline reference textbook chapter 10 D. Mount Lectures 13 and 24 segment trees ⇒ stabbing queries ⇒ rectangle intersection interval trees ⇒ improvement higher dimension Lecture 5:Segment trees and interval trees – p.2/37 Stabbing queries orthogonal range searching: data points, query rectangle stabbing problem: data rectangles, query point in one dimension input: a set of n intervals, a query point q output: the k intervals that contain q in IRd a box b is isothetic iff it can be written b = [x1, x ′ 1]× [x2, x ′ 2]× . . .× [xd, x ′ d] in other words it is axis–parallel input: a set of n isothetic boxes, a query point q output: the k boxes that contain q Lecture 5:Segment trees and interval trees – p.3/37 Motivation in graphics and databases, objects are often stored in their bounding box Object Bounding box query: which objects does point x belong to? first find objects whose bounding boxes intersect x Lecture 5:Segment trees and interval trees – p.4/37 Segment trees Lecture 5:Segment trees and interval trees – p.5/37 Segment tree a data structure to store intervals, or segments in IR2 allows to answer stabbing queries in IR2: report the segments that intersect a query vertical line l reported reported reported l query time: O(log n + k) space usage: O(n log n) preprocessing time: O(n log n) Lecture 5:Segment trees and interval trees – p.6/37 Notations let S = (s1, s2, . . . sn) be a set of segments in IR2 let E be the set of the x–coordinates of the endpoints of the segments of S we assume general position, that is: |E| = 2n first sort E in increasing order E = {e1 < e2 < . . . e2n} Lecture 5:Segment trees and interval trees – p.7/37 Atomic intervals E splits IR into 2n + 1 atomic intervals: [−∞, e1] [ei, ei+1] for i ∈ {1, 2, . . . 2n− 1} [e2n,∞] these are the leaves of the segment tree S E Lecture 5:Segment trees and interval trees – p.8/37 Internal nodes the segment tree T is a balanced binary tree each internal node u with children v and v′ is associated with an interval Iu = Iv ∪ I ′v an elementary interval is an interval associated with a node of T (it can be an atomic interval) Iu Iv Iv′ v v′ u Lecture 5:Segment trees and interval trees – p.9/37 Example E S root Lecture 5:Segment trees and interval trees – p.10/37 Partitioning a segment let s ∈ S be a segment whose endpoints have x–coordinates ei and ej [ei, ej ] is split into several elementary intervals they are chosen as close as possible to the root s is stored in each node associated with these elementary intervals E s root Lecture 5:Segment trees and interval trees – p.11/37 Standard lists each node u is associated with a standard list Lu let ei < ej be the x–coordinates of the endpoints of s ∈ S then s is stored in Lu iff Iu ⊂ [ei, ej ] and Iparent(u) 6⊂ [ei, ej ] (see previous slide and next slide) Lecture 5:Segment trees and interval trees – p.12/37 Example root Lecture 5:Segment trees and interval trees – p.13/37 Answering a stabbing query root l Lecture 5:Segment trees and interval trees – p.14/37 Answering a stabbing query Algorithm ReportStabbing(u, xl) Input: root u of T , x–coordinate of l Output: segments in S that cross l 1. if u == NULL 2. then return 3. output Lu 4. if xl ∈ Iu.left 5. then ReportStabbing(u.left, xl) 6. if xl ∈ Iu.right 7. then ReportStabbing(u.right, xl) it clearly takes O(k + log n) time Lecture 5:Segment trees and interval trees – p.15/37 Inserting a segment E s root Lecture 5:Segment trees and interval trees – p.16/37 Insertion in a segment tree Algorithm Insert(u, s) Input: root u of T , segment s. Endpoints of s have x–coordinates x− < x+ 1. if Iu ⊂ [x−, x+] 2. then insert s into Lu 3. else 4. if [x−, x+] ∩ Iu.left 6= ∅ 5. then Insert(u.left, s) 6. if [x−, x+] ∩ Iu.right 6= ∅ 7. then Insert(u.right, s) Lecture 5:Segment trees and interval trees – p.17/37 Property s is stored at most twice at each level of T proof: by contradiction if s stored at more than 2 nodes at level i let u be the leftmost such node, u′ be the rightmost let v be another node at level i containing s u v u′ s v.parent then Iv.parent ⊂ [x−, x+] so s cannot be stored at v Lecture 5:Segment trees and interval trees – p.18/37 Analysis property of previous slide implies space usage: O(n log n) insertion in O(log n) time (similar proof: four nodes at most are visited at each level) actually space usage is Θ(n log n) (example?) query time: O(k + log n) preprocessing sort endpoints: Θ(n log n) time build empty segment tree over these endpoints: O(n) time insert n segments into T : O(n log n) time overall: Θ(n log n) preprocessing time Lecture 5:Segment trees and interval trees – p.19/37 Rectangle intersection Lecture 5:Segment trees and interval trees – p.20/37 Problem statement input: a set B of n isothetic boxes in IR2 output: all the intersecting pairs in B2 using segment trees, we give an O(n log n + k) time algorithm when k is the number of intersecting pairs note: this is optimal note: faster than our line segment intersection algorithm space usage: Θ(n log n) due to segment trees space usage is not optimal (O(n) is possible with optimal query time and preprocessing time) Lecture 5:Segment trees and interval trees – p.21/37 Example b4 b3 b1 b2 b5 output: (b1, b3),(b2, b3),(b2, b4),(b3, b4) Lecture 5:Segment trees and interval trees – p.22/37 Two kinds of intersections overlap intersecting edges ⇒ reduces to intersection reporting for isothetic segments inclusion we can find them using stabbing queries Lecture 5:Segment trees and interval trees – p.23/37 Reporting overlaps equivalent to reporting intersecting edges plane sweep approach sweep line status: BBST containing the horizontal line segments that intersect the sweep line, by increasing y–coordinates each time a vertical line segment is encountered, report intersection by range searching in the BBST preprocessing time: O(n log n) for sorting endpoints running time: O(k + n log n) Lecture 5:Segment trees and interval trees – p.24/37 Reporting inclusions still using plane sweep sweep line status: the boxes that intersect the sweep line l, in a segment tree with respect to y–coordinates the endpoints are the y–coordinates of the horizontal edges of the boxes at a given time, only rectangles that intersect l are in the segment tree we can perform insertion and deletions in a segment tree in O(log n) time each time a vertex of a box is encountered, perform a stabbing query in the segment tree Lecture 5:Segment trees and interval trees – p.25/37 Remarks at each step a box intersection can be reported several times in addition there can be overlap and vertex stabbing a box at the same time to obtain each intersecting pair only once, make some simple checks (how?) Lecture 5:Segment trees and interval trees – p.26/37 Interval trees Lecture 5:Segment trees and interval trees – p.27/37 Introduction interval trees allow to perform stabbing queries in one dimension query time: O(k + log n) preprocessing time: O(n log n) space: O(n) reference: D. Mount notes, page 100 (vertical line stabbing queries) to page 103 (not including vertical segment stabbing queries) Lecture 5:Segment trees and interval trees – p.28/37 Preliminary let xmed be the median of E Sl: segments of S that are completely to the left of xmed Smed: segments of S that contain xmed Sr: segments of S that are completely to the right of xmed xmed Smed Sr Sl Lecture 5:Segment trees and interval trees – p.29/37 Data structure recursive data structure left child of the root: interval tree storing Sl right child of the root: interval tree storing Sr at the root of the interval tree, we store Smed in two lists ML is sorted according to the coordinate of the left endpoint (in increasing order) MR is sorted according to the coordinate of the right endpoint (in decreasing order) Lecture 5:Segment trees and interval trees – p.30/37 Example s1 s2s3 s5 s7 s4 s6 Interval tree on s3 and s5 Interval tree on Ml = (s4, s6, s1) Mr = (s1, s4, s6) s2 and s7 Lecture 5:Segment trees and interval trees – p.31/37 Stabbing queries query: xq, find the intervals that contain xq if xq < xmed then Scan Ml in increasing order, and report segments that are stabbed. When xq becomes smaller than the x–coordinate of the current left endpoint, stop. recurse on Sl if xq > xmed analogous, but on the right side Lecture 5:Segment trees and interval trees – p.32/37 Analysis query time size of the subtree divided by at least two at each level scanning through Ml or Mr: proportional to the number of reported intervals conclusion: O(k + log n) time space usage: O(n) (each segment is stored in two lists, and the tree is balanced) preprocessing time: easy to do it in O(n log n) time Lecture 5:Segment trees and interval trees – p.33/37 Stabbing queries in higher dimension Lecture 5:Segment trees and interval trees – p.34/37 Approach in IRd, a set B of n boxes for a query point q find all the boxes that contain it we use a multi–level segment tree inductive definition, induction on d first, we store B in a segment tree T with respect to x1–coordinate for all node u of T , associate a (d− 1)–dimensional multi–level segment tree over Lu, with respect to (x2, x3 . . . xd) Lecture 5:Segment trees and interval trees – p.35/37 Performing queries search for q in T for all nodes in the search path, query recursively the (d− 1)–dimensional multi–level segment tree there are log n such queries by induction on d, we can prove that query time: O(k + logd n) space usage: O(n logd n) preprocessing time : O(n logd n) Lecture 5:Segment trees and interval trees – p.36/37 Improvements fractional cascading at the deepest level of the tree: gains a factor log n on the query time bound interval trees at the deepest level: gains log n on the space bound Lecture 5:Segment trees and interval trees – p.37/37 Outline Stabbing queries Motivation Segment trees Segment tree Notations Atomic intervals Internal nodes Example Partitioning a segment Standard lists Example Answering a stabbing query Answering a stabbing query Inserting a segment Insertion in a segment tree Property Analysis Rectangle intersection Problem statement Example Two kinds of intersections Reporting overlaps Reporting inclusions Remarks Interval trees Introduction Preliminary Data structure Example Stabbing queries Analysis Stabbing queries in higher dimension Approach Performing queries Improvements