Data Structures19 sections · 729 units
Open in Course

Challenge: Design Your Solution

Practice choosing techniques

For each problem, decide: sqrt decomposition, MO's algorithm, or segment tree?

1.1. Range sum with point updates, 10510^5 operations: Segment tree (log factor matters at scale)

2.2. Count distinct in range, offline, 10510^5 queries: MO's algorithm (segment tree can't do this easily)

3.3. Range min with occasional updates, quick implementation: Sqrt decomposition (simplicity wins)

4.4. Range add with range sum, 10610^6 operations: Segment tree with lazy (sqrt is too slow) These choices become intuitive with practice.