Data Structure Mastery Ladder

What This Ladder Trains: Fluency with data structures from basic containers to advanced range-query structures. You'll progress through maps and frequency counting, stack/queue tricks, monotonic stacks, BITs (Fenwick trees), segment trees, and lazy propagation. By the end, you should confidently pick the right data structure for a problem and implement it under time pressure.

Quick Revisit

• SKILL FOCUS: data structure mastery -- maps and stacks through segment trees and lazy propagation
• DIFFICULTY: 1200--2100
• PROBLEMS: 15
• PREREQUISITE: Data Structures and Data Structure Selection Guide

---

Contents

• Warm-Up (1200-1400)
• Core (1400-1600)
• Advanced (1600-1900)
• How to Use This Ladder

---

Warm-Up (≈1200-1600)

Maps, sets, basic stack/queue usage, and difference arrays. Tier labels here are approximate — the Core tier reaches 1900, the Advanced tier 2100 — calibrated to the data-structure idea, not the raw rating. Read the labels as "structural difficulty," not "Codeforces rating." Don't recalibrate self-worth from them.

#	Problem	Rating	Hint
1	Delete Two Elements	1200	Hint Compute the required pair sum from the total. Count how many pairs match using a frequency map.
2	Ball in Berland	1400	Hint For each pair, count incompatible pairs via set sizes. Total pairs minus conflicts = answer.
3	Stack of Presents	1400	Hint For each friend's wish list, find the deepest gift in the stack. Cost = items above it (remove and re-stack).
4	Little Girl and Maximum Sum	1500	Hint Use a difference array to count query frequency per position. Sort frequencies and values greedily.
5	Chocolate Bunny	1600	Hint (note: this is an interactive problem, included for ordered-reasoning training) Not a classical data structure exercise — it lives here because the elimination logic is the same shape as a multiset shrink. Query pairs (i,j) and (j,i); the mod results identify which position holds the smaller value, eliminating one element per query. If you'd rather skip interactive work for now, substitute a multiset-based problem from the Core tier.

If you struggled here, review Chapter 0: Fundamentals -- basic data structures -- and Chapter 1: Essential Techniques -- difference arrays.

---

Core (1400-1600)

Monotonic stacks, multiset tricks, segment trees, and BIT fundamentals.

#	Problem	Rating	Hint
6	Xenia and Bit Operations	1700	Hint Build a segment tree where alternating levels apply OR and XOR. Point update + root query.
7	Minimum Array	1700	Hint For each a[i], find the smallest b[j] such that (a[i]+b[j]) mod n is minimized. Use a multiset with lower_bound.
8	Constant Palindrome Sum	1700	Hint For each pair (a[i], a[n-1-i]), compute the range of sums achievable with 0, 1, or 2 changes. Sweep with a difference array.
9	Skyscrapers	1900	Hint For each index as the peak, compute max sum using prefix/suffix with a monotonic stack to enforce non-increasing constraints.
10	Multiset	1900	Hint Use a BIT (Fenwick tree) to maintain the sorted multiset. Delete the k-th smallest by binary-searching the BIT prefix sums.

If you struggled here, review Chapter 2: Data Structures -- segment trees, BITs, and monotonic stacks.

---

Advanced (1600-1900)

BIT inversions, advanced segment trees, and lazy propagation.

#	Problem	Rating	Hint
11	Pashmak and Parmida's problem	1800	Hint Compute f(1..i,a[i]) and f(i..n,a[i]) arrays. Count inversions (f_left[i] > f_right[j] for i < j) with a BIT.
12	Enemy is weak	1900	Hint Count triples (i<j<k) with a[i]>a[j]>a[k]. For each j, multiply "larger elements before j" x "smaller elements after j" using a BIT.
13	Sereja and Brackets	2000	Hint Segment tree storing (matched, unmatched_open, unmatched_close) per node. Merge by cancelling open with close.
14	The Child and Sequence	2000	Hint Segment tree with range mod and range sum. Mod only matters when mod_value < current max -- track max per node to skip no-op updates.
15	Strange Array	2100	Hint For each element, count values <= it vs > it in any subarray. Use a segment tree with range updates processed via sweep.

If you struggled here, review Chapter 2: Data Structures -- lazy propagation and merge-sort trees -- and Chapter 9: Offline Techniques.

---

How to Use This Ladder

Before coding any problem, write a four-line operation inventory. This is the connection between the problem and the Data Structure Selection Guide, and it does more to pick the right tool than any algorithm knowledge:

1. Required operations: what do you actually need to do? (insert, query-range-sum, find-kth, find-min-in-range, …)
2. Update / query pattern: point or range updates? point or range queries? interleaved or batched?
3. Online or offline: must each query be answered before the next is read, or can you reorder?
4. Does ordering matter: is the sequence of operations meaningful, or only the final result?

Many learners pick the fanciest tool they know. The inventory forces the question "could I have used a simpler data structure?" before you've already committed to a segment tree.

Then:

1. Implement from scratch. Do not copy templates -- build your BIT and segment tree line by line until the structure is automatic.
2. Time-box: 30 min for Warm-Up, 45 min for Core, 60-75 min for Advanced.
3. After each problem, revisit the operation inventory. Did you use what you said you needed? Could a simpler structure have worked?
4. Build a personal library. By the end, you should have tested implementations of: BIT (point update, range query), segment tree (with and without lazy), monotonic stack, and multiset usage patterns.
5. Supplement weak areas. If segment tree problems are hard, solve 3-5 more from the 1400-->1700 ladder segment tree section.

Progression Check

• [ ] Warm-Up: solved >= 4/5 without hints
• [ ] Core: solved >= 3/5 within time limits
• [ ] Advanced: attempted all 5, solved >= 2
• [ ] Can implement BIT and basic segment tree from memory in under 15 minutes
• [ ] Understand when lazy propagation is needed vs when it's overkill

---

See also: Data Structures | Data Structure Selection Guide | Rating ladders