📜 WAYPOINT LESSON
Checkpoint — Fenwick Mastery
⭐ beginner⏳ 25 min read📍 Lesson 134 of 281
Two jobs on one tree: find the k-th empty slot by binary-lifting descent, then answer range-occupancy counts by prefix difference. The broken descent overshoots on the very first op.
Checkpoint — Fenwick. n ≤ 200 000 ô trống, q ≤ 200 000 thao tác:
1 k = chiếm ô trống thứ k (in vị trí); 2 l r = in số ô đã chiếm trong
[l, r]. Một cây Fenwick làm cả hai: đi xuống luỹ thừa 2 cho op 1, hiệu
tiền tố cho op 2. Lỗi đi xuống (quên trừ rem) vượt đích ngay thao tác đầu.