Videos / DSA

Episode 22 of 22 · DSA, end to end

Segment trees and ordered sets: range queries that keep up with updates

Chapters

1. A range and a change0:00
2. Prefix sums, in one line0:17
3. One write, whole tail0:34
4. Put numbers on it0:50
5. Perfect at one thing each1:07
6. Refuse to be perfect1:24
7. A knockout draw1:40
8. A node owns a range1:57
9. How tall is it2:13
10. A tree in a flat array2:30
11. Two nodes per level, at most2:45
12. It was never addition3:00
13. Nested boxes3:17
14. The build, in seven lines3:34
15. Three cases3:49
16. The query, in code4:07
17. One leaf, one path4:25
18. Update, and the flat version4:43
19. A note on the drawer5:00
20. Adding to a whole range5:16
21. Leave a tag5:34
22. Pay on descent5:50
23. Watch the numbers move6:06
24. Two ways lazy goes wrong6:23
25. Rulers of two6:40
26. The lowest set bit6:54
27. Walking a prefix down7:12
28. And an update up7:29
29. Eight lines of it7:47
30. What it gives up8:04
31. A leaderboard8:21
32. Rank and select8:36
33. The same tree, over values8:54
34. Select descends9:09
35. The tree you get free9:27
36. Which one, when9:46
37. The whole thing10:04

Segment trees and ordered sets: range queries that keep up with updates. Here is a row of numbers. Eight of them. Somebody asks for the total between position two and position five. Then somebody changes position four. Then they ask again. Two operation

Mark as watchedSaved in this browser only.