Part VII — Advanced Data Structures

You’ve conquered arrays, linked lists, hash maps, trees, heaps, and graphs. These cover the vast majority of interview questions — and yet certain problems resist every tool in that toolkit. When an interviewer asks you to handle range sum queries with dynamic updates, track connected components as edges arrive one by one, or maintain a sorted collection without the complexity of self-balancing trees, standard structures buckle under the weight.

This part of the book arms you with three specialized data structures that unlock entire problem categories.

When Standard Structures Fall Short

Consider these scenarios:

Range queries with updates. You have an array of integers. You need to answer “what is the sum from index 3 to index 700?” — and elements change between queries. A plain array gives you O(1) updates but O(n) queries, or O(1) queries with a prefix sum array but O(n) updates to maintain it. Neither scales when you face 100,000 of each operation.

Dynamic connectivity. Edges arrive in a stream. After each edge, you need to answer “are nodes A and B in the same connected component?” and “how many components remain?” A full graph traversal after every edge insertion is prohibitively expensive.

Ordered operations without complexity. Balanced BSTs (AVL, Red-Black) deliver O(log n) search, insert, and delete — but their rotation logic is notoriously error-prone to implement from scratch. What if you could achieve the same expected performance with a structure that never rotates anything?

These three scenarios map directly to the three structures you’ll master in this part.

The Three Structures

Fenwick Trees (Binary Indexed Trees)

A Fenwick Tree compresses prefix sum information into an array of the same size as your input, using a clever bit manipulation trick. Every index stores a partial sum covering a range determined by the lowest set bit in that index’s binary representation. This delivers O(log n) point updates and O(log n) prefix queries — a massive improvement over the naive trade-off.

Fenwick Trees appear in problems involving mutable range sums, counting inversions, and coordinate compression tasks. Their code footprint is remarkably small — often under 20 lines for a complete implementation.

Disjoint Set Union (Union-Find)

Union-Find represents a collection of disjoint sets as a forest of trees, where each tree’s root identifies the set. Two optimizations — path compression (flattening the tree during find operations) and union by rank (attaching shorter trees under taller ones) — reduce the amortized cost per operation to O(α(n)), where α is the inverse Ackermann function. For all practical input sizes, this is effectively constant time.

Union-Find powers Kruskal’s minimum spanning tree algorithm, dynamic graph connectivity queries, accounts merge problems, and cycle detection in undirected graphs.

Skip Lists

A Skip List layers multiple levels of linked lists on top of each other, where each higher level acts as an “express lane” skipping over elements. Instead of using rotations to maintain balance, Skip Lists use randomized level assignment — each element is promoted to the next level with probability p (typically 0.5). This probabilistic approach yields expected O(log n) search, insert, and delete without any structural rebalancing.

Java’s ConcurrentSkipListMap uses this structure internally, making it a practical choice for concurrent sorted map operations. Redis uses Skip Lists to power its sorted set data type — a real-world endorsement of the structure’s effectiveness.

What Lies Ahead

Each sub-chapter delivers a complete, production-quality Java 25 implementation alongside the intuition behind every design decision. You’ll work through classic interview problems for each structure, learn the comparison points interviewers expect you to articulate, and develop the judgment to pick the right structure when a problem demands more than the basics.

Let’s start with the structure that packs the most power into the fewest lines of code.