(1 Starting point: Bit vector Bit vector y stores for eachxE U lifx∈S lO ifx g s Example:l=16;n=4;S={1,9,10,15} 0100000001100001 0123456789101112131415 Insert/Delete run in o(1)time Successor/Predecessor run in O(u) worst-case time c 2001 by erik D. Demaine Introduction to Agorithms Day 23 L12.5© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.5 (1) Starting point: Bit vector Bit vector v stores, for each x ∈ U, 1 if x ∈ S 0 if x ∉ S vx = Insert/Delete run in O(1) time. Successor/Predecessor run in O(u) worst-case time. Example: u = 16; n = 4; S = {1, 9, 10, 15}. 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15