Lesson 07.2
Availability bitmaps & segment trees
An availability bitmap keeps one bit per hotel for each night, so a city search ANDs the stay's nights together; a segment tree stores pre-combined blocks of nights so long stays need only a few ANDs.
Eight hotels, one yes/no list per night
Ava and Ben run a search website for the eight hotels in town. The computer can check every hotel on every night, or it can keep one yes/no list for each night and combine the lists.
In this lesson you'll
- 1Follow one run and learn how to read the picture
- 2Predict what changes before revealing the result
- 3Search a 4-night stay and stay inside the budget