When Algorithms Need Memory

You are here: Ch 1 (Essential Techniques) → Ch 2 (Data Structures) | Core Path

What You've Learned

Chapter 1 gave you the core moves: two pointers, sliding window, prefix sums, binary search, greedy, complete search, divide and conquer. On static input these techniques are devastatingly effective—enough to crack most CF 1000–1500 problems with just these tools.

But the operative word is static.

Where Static Breaks

You solved the range-sum problem with prefix sums in $O (1)$ per query. Then the problem changes: "After each query, one element gets updated." Your prefix sums are useless now.

Why? Because prefix sums are a snapshot. They capture the array's state at build time. Change one element, and every prefix from that index onward is wrong. Rebuilding costs $O (n)$ , and if you're rebuilding after every update, you're back to $O (n)$ per query—exactly the brute force you were trying to avoid.

This isn't a flaw in prefix sums. It's a fundamental limitation: techniques that precompute a static answer can't handle dynamic data.

And dynamic data is everywhere. Scores change. Edges get added. Elements get inserted and deleted. The real world doesn't hold still while you preprocess it.

Here's a concrete way to feel the pain. Imagine a competitive programming judge sending you this input:

text

5 5
1 3 2 7 4
Q 2 4       -> sum of a[2..4] = 3+2+7 = 12
U 3 10      -> set a[3] = 10
Q 2 4       -> sum of a[2..4] = 3+10+7 = 20
U 1 5       -> set a[1] = 5
Q 1 5       -> sum of a[1..5] = 5+3+10+7+4 = 29

Queries and updates, interleaved. Your prefix sum array is stale after the first update. You could rebuild it each time, but that's $O (n)$ per update—and with $10^{5}$ of each, you're dead.

The Breaking Points

Three problems where Chapter 1 gets you almost there, then hits a wall.

1. Range sums with updates. Prefix sums answer range queries in $O (1)$ . But a single point update invalidates $O (n)$ prefixes. You need a structure that answers range queries in $O (\log n)$ and handles updates in $O (\log n)$ . That's a segment tree—or its leaner cousin, the Fenwick tree (BIT). The key idea: instead of storing every prefix, store partial sums over a clever hierarchy of intervals. Updates touch only $O (\log n)$ nodes.

Try writing the brute-force update yourself:

cpp

// After a[pos] changes, recompute ALL prefixes from pos onward
for (int i = pos; i < n; i++) prefix[i+1] = prefix[i] + a[i];

That's $O (n)$ per update. With $10^{5}$ updates interleaved with $10^{5}$ queries, you're at $10^{10}$ operations. A segment tree does both in $O (\log n)$ , for a total of $O (n \log n)$ . Same problem, same input, five orders of magnitude faster.

2. K-th smallest in a changing collection. You can sort an array and binary search for the k-th element. But what if elements keep getting added and removed? Re-sorting after every operation is $O (n \log n)$ . You need a structure that maintains sorted order under insertions and deletions. A balanced BST—or a BIT with binary lifting—answers k-th order queries in $O (\log n)$ even as the set changes beneath you.

The key realization: sorting is a one-time operation. When the data is alive—growing, shrinking, mutating—you need a structure that is the sorted order, at all times.

3. Connected components as edges arrive online. You're processing edges one by one. "Are nodes u and v in the same component?" With Chapter 1 tools, you'd run BFS or DFS from scratch each time— $O (n + m)$ per query. But a Disjoint Set Union (DSU) tracks components incrementally. Each union and find is nearly $O (1)$ amortized. You never recompute from scratch because the structure remembers what it's already seen.

This is the pattern at its starkest: the Chapter 1 approach—run BFS from scratch—is correct but too slow because it refuses to remember anything between queries.

What Data Structures Actually Are

The common thread: in each case, the Chapter 1 technique works perfectly on static input. The problem is change over time, and the solution is always the same idea—build a structure that maintains precomputed answers as the data evolves.

A segment tree is a prefix sum that can handle updates. A DSU is a connected-components algorithm that doesn't forget. A priority queue is a "find the minimum" operation that stays correct as elements arrive.

Data structures are algorithms with memory. They hold state so you don't recompute from scratch on every query.

That is a real conceptual shift. In Chapter 1, you thought about algorithms—sequences of steps that transform input to output. In Chapter 2, you'll think about objects—containers that maintain invariants as operations happen to them. The algorithm doesn't run once and finish; it lives, responds, adapts.

What to Expect

The engineering complexity is genuinely higher here. Chapter 1 techniques each fit in your head as a paragraph of logic—two pointers, sliding window, prefix sums. Data structures have more machinery: a segment tree has a build phase, a query function, and an update function, and a lazy segment tree adds deferred propagation on top of that. They're not harder because they require more cleverness—they're harder because they require more engineering. More moving parts, more edge cases, more code.

But the payoff matches the investment. A segment tree with lazy propagation answers any associative range query with range updates in $O (\log n)$ —one structure, hundreds of problems. A DSU with path compression and union by rank turns $O (n)$ connectivity checks into nearly $O (1)$ . Master these structures once and they pay dividends across your entire competitive programming career.

That shift—from static computation to dynamic maintenance—is what separates a 1500-rated problem from an 1800-rated one. Let's make it.

Before You Move On

Can you confidently:

[ ] Apply two pointers and sliding window to subarray problems?
[ ] Use prefix sums and difference arrays for range queries on static data?
[ ] Recognize when binary search applies to an answer space (not just an array)?
[ ] Write a correct greedy solution and argue why it's optimal?
[ ] Use divide and conquer for merge-sort-style counting problems?
[ ] Estimate complexity and choose the right technique before coding?

If not, revisit Chapter 1 before continuing. Data structures assume you're fluent with the underlying techniques.

Key Files

Chapter 1 (just completed):

Prefix Sums—you'll see these evolve into Fenwick trees
Binary Search—binary lifting extends this idea
Sorting and Searching—sorting becomes maintenance
Greedy—greedy + priority queue is a key combination

Chapter 2 (starting now):

Stack, Queue, Deque—start here
Monotonic Stack—your first "structural" data structure
Union-Find (DSU)—the third breaking point, solved
Segment Tree—the first breaking point, solved

Practice: Ladder: Data Structures

Next: Chapter 2—Data Structures

When Algorithms Need Memory ​

What You've Learned ​

Where Static Breaks ​

The Breaking Points ​

What Data Structures Actually Are ​

What to Expect ​

Before You Move On ​

Key Files ​