Advanced Data Structures
You have now covered the major fundamental data structures:
Array String Linked List Stack Queue Deque Hashing Tree Binary Tree BST Heap Priority Queue Trie Graph
Now we move to Advanced Data Structures.
Advanced data structures are structures designed to handle more complex operations efficiently, especially when basic structures are too slow.
The important ones to know are:
1. AVL Tree 2. Red-Black Tree 3. Segment Tree 4. Fenwick Tree / Binary Indexed Tree 5. Disjoint Set Union (DSU) 6. B-Tree / B+ Tree 7. Suffix Array 8. Suffix Tree 9. Sparse Table 10. Treap 11. Monotonic Stack / Queue 12. Bloom Filter 13. Skip List
You don't need to memorize all of these immediately. The most important for DSA/problem solving are usually:
AVL / Red-Black Tree, Segment Tree, Fenwick Tree, DSU, Sparse Table, and advanced string structures.
1. Why Do We Need Advanced Data Structures?
Suppose you have an array:
[2, 5, 1, 8, 6, 3, 7]
You need to repeatedly perform:
Update index 3 Find sum from index 2 to 6 Update index 5 Find minimum from index 1 to 7 ...
A normal array may require:
O(n)
for some queries.
If there are:
100,000 elements 100,000 queries
then:
100,000 × 100,000 = 10,000,000,000
operations could be far too much.
Advanced data structures help reduce operations such as:
O(n) → O(log n)
or sometimes:
O(n) → O(1)
depending on the problem.
2. Advanced Data Structures Overview
Think of them according to what problem they solve:
| Data Structure | Main Purpose |
|---|---|
| AVL Tree | Balanced searching |
| Red-Black Tree | Balanced searching |
| Segment Tree | Range queries + updates |
| Fenwick Tree | Prefix/range sums + updates |
| DSU | Dynamic connectivity |
| Sparse Table | Fast static range queries |
| B-Tree | Disk/database indexing |
| B+ Tree | Database/file-system indexing |
| Suffix Array | String processing |
| Suffix Tree | Advanced string processing |
| Treap | Randomized balanced BST |
| Skip List | Probabilistic ordered structure |
| Bloom Filter | Fast probabilistic membership |
| Monotonic Stack | Next greater/smaller problems |
| Monotonic Queue | Sliding-window problems |
Let's understand them one by one.
3. AVL Tree
You already learned BST.
A normal BST can become badly unbalanced.
For example, inserting:
1 2 3 4 5
could create:
1 \ 2 \ 3 \ 4 \ 5
This behaves almost like a linked list.
Search becomes:
O(n)
instead of:
O(log n)
AVL Tree
An AVL Tree is a self-balancing Binary Search Tree.
The height difference between the left and right subtree of every node is kept within a small bound.
The balance factor is:
Balance Factor = height(left subtree) - height(right subtree)
For an AVL tree:
-1 ≤ Balance Factor ≤ 1
So:
Balance Factor = -1 Balance Factor = 0 Balance Factor = 1
are valid.
4. AVL Rotations
When inserting a node makes the tree unbalanced, we perform rotations.
Four common cases:
LL RR LR RL
LL Case
30 / 20 / 10
Right rotation:
20 / \ 10 30
RR Case
10 \ 20 \ 30
Left rotation:
20 / \ 10 30
LR Case
30 / 10 \ 20
First:
Left rotation
then:
Right rotation
Result:
20 / \ 10 30
RL Case
Mirror of LR:
10 \ 30 / 20
Apply:
Right rotation
then:
Left rotation
5. AVL Complexity
Because AVL maintains balance:
| Operation | Complexity |
|---|---|
| Search | O(log n) |
| Insert | O(log n) |
| Delete | O(log n) |
This is the major advantage over an ordinary unbalanced BST.
6. Red-Black Tree
A Red-Black Tree is another self-balancing BST.
Instead of strictly maintaining subtree height differences like AVL, each node has a color:
RED BLACK
The tree follows rules that prevent it from becoming too unbalanced.
One important property is that the longest path is bounded relative to the shortest path.
Therefore the height remains:
O(log n)
7. Red-Black Tree Properties
Important rules include:
- Every node is either red or black.
- The root is black.
- A red node cannot have a red child.
- Every path from a node to its relevant NIL leaves has the same number of black nodes.
- NIL/null leaves are treated as black.
When insertion or deletion violates these properties, the tree uses:
Rotations + Recoloring
to restore balance.
8. AVL vs Red-Black Tree
| Feature | AVL | Red-Black |
|---|---|---|
| Balance | More strict | Less strict |
| Search | Very good | Very good |
| Insert/Delete | More rotations possible | Usually fewer |
| Height | Smaller | Slightly larger |
| Use case | Search-heavy | Frequent updates |
A practical example is the C++ STL:
map set multimap multiset
are commonly implemented using a balanced tree, typically a Red-Black Tree.
9. Segment Tree
Now we reach one of the most important advanced data structures.
A Segment Tree is mainly used for:
Range queries + updates
Suppose:
arr = [1, 3, 5, 7, 9, 11]
You want:
sum(1, 4)
meaning:
3 + 5 + 7 + 9
If you calculate directly:
O(n)
per query.
A Segment Tree can answer range queries in:
O(log n)
and updates in:
O(log n)
10. Segment Tree Structure
For:
[1, 3, 5, 7]
A sum segment tree could look conceptually like:
[1,3,5,7] sum = 16 / \ [1,3] [5,7] / \ / \ 1 3 5 7
Each node stores information about an interval.
For example:
[1,3] → sum 4 [5,7] → sum 12
11. Segment Tree Operations
Typical operations:
Build
Construct the tree:
O(n)
Range Query
For example:
sum(2, 5)
Complexity:
O(log n)
Update
Change:
arr[3] = 10
Complexity:
O(log n)
12. Segment Tree C++ Example
#include <iostream> #include <vector> using namespace std; class SegmentTree { vector<int> tree; int n; void build(vector<int>& arr, int node, int start, int end) { if (start == end) { tree[node] = arr[start]; return; } int mid = (start + end) / 2; build(arr, 2 * node, start, mid); build(arr, 2 * node + 1, mid + 1, end); tree[node] = tree[2 * node] + tree[2 * node + 1]; } int query( int node, int start, int end, int l, int r ) { if (r < start || end < l) return 0; if (l <= start && end <= r) return tree[node]; int mid = (start + end) / 2; return query(2 * node, start, mid, l, r) + query(2 * node + 1, mid + 1, end, l, r); } public: SegmentTree(vector<int>& arr) { n = arr.size(); tree.resize(4 * n); build(arr, 1, 0, n - 1); } int rangeSum(int l, int r) { return query(1, 0, n - 1, l, r); } };
The exact implementation changes depending on whether you need:
- sum
- minimum
- maximum
- GCD
- XOR
- custom information
13. Fenwick Tree
A Fenwick Tree, also called a Binary Indexed Tree (BIT), is another structure for range/prefix queries.
It is generally simpler than a Segment Tree when the operation fits its structure.
Typical use:
Point update + Prefix sum
Both:
O(log n)
14. Fenwick Tree Idea
Suppose:
[1, 2, 3, 4, 5]
Instead of storing every possible range, a Fenwick Tree stores carefully selected partial sums.
The important bit trick is:
i & -i
This extracts the lowest set bit.
That determines how much range a Fenwick Tree node represents.
15. Fenwick Tree C++ Implementation
class FenwickTree { vector<int> bit; int n; public: FenwickTree(int n) { this->n = n; bit.resize(n + 1, 0); } void update(int index, int value) { for (; index <= n; index += index & -index) { bit[index] += value; } } int query(int index) { int sum = 0; for (; index > 0; index -= index & -index) { sum += bit[index]; } return sum; } };
Complexity:
Update → O(log n) Prefix Sum → O(log n)
16. Segment Tree vs Fenwick Tree
| Feature | Segment Tree | Fenwick Tree |
|---|---|---|
| Range sum | Yes | Yes |
| Point update | Yes | Yes |
| Prefix sum | Yes | Yes |
| Range minimum | Yes | Not as generally |
| Range maximum | Yes | Not as generally |
| Complex operations | More flexible | More limited |
| Memory | O(n) | O(n) |
| Implementation | More complex | Simpler |
Easy rule
Use:
Fenwick Tree
when you mainly need:
prefix/range sums + point updates
Use:
Segment Tree
when you need more complicated range queries or updates.
17. Disjoint Set Union — DSU
Another extremely important advanced data structure is:
Disjoint Set Union
Also called:
- Union-Find
- DSU
It manages multiple groups/sets.
Main operations:
Find Union
18. Real-Life Example of DSU
Imagine students:
A B C D E
Initially:
{A} {B} {C} {D} {E}
Now:
Union(A, B)
becomes:
{A, B} {C} {D} {E}
Then:
Union(B, C)
becomes:
{A, B, C} {D} {E}
DSU efficiently determines:
Are A and C in the same group?
19. DSU Operations
Find
Find the representative/leader of a set.
find(x)
Union
Merge two sets:
union(a, b)
20. DSU Optimization
Two major optimizations make DSU extremely fast:
Path Compression
During find(), connect nodes directly toward the root.
Union by Size/Rank
Attach the smaller tree to the larger tree.
With both optimizations, operations are effectively:
O(α(n))
amortized, where α(n) is the inverse Ackermann function and grows extraordinarily slowly.
For practical purposes:
≈ O(1)
21. DSU C++ Implementation
class DSU { vector<int> parent; vector<int> size; public: DSU(int n) { parent.resize(n); size.resize(n, 1); for (int i = 0; i < n; i++) { parent[i] = i; } } int find(int x) { if (parent[x] == x) return x; return parent[x] = find(parent[x]); } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (size[a] < size[b]) swap(a, b); parent[b] = a; size[a] += size[b]; } bool same(int a, int b) { return find(a) == find(b); } };
22. DSU Applications
DSU is heavily used in graph problems.
1. Kruskal's Algorithm
You studied MST in Greedy.
Kruskal needs DSU to detect whether adding an edge would create a cycle.
Sort edges ↓ Smallest edge ↓ Same component? ↓ No → Add edge Yes → Skip
2. Cycle Detection
DSU can detect cycles in undirected graphs.
3. Connected Components
Track which vertices belong to the same component.
4. Network Connectivity
Determine whether two nodes belong to the same connected group.
23. Sparse Table
A Sparse Table is useful for answering static range queries very quickly.
"Static" means:
The array does not change after preprocessing.
For example:
[4, 2, 7, 1, 9, 3]
You might repeatedly ask:
minimum from L to R
24. Sparse Table Complexity
For operations such as Range Minimum Query:
Preprocessing → O(n log n) Query → O(1)
This is extremely fast for queries.
But:
Update
is not its strength.
So:
Static array → Sparse Table Dynamic array → Segment/Fenwick Tree
is a useful rule.
25. B-Tree
A B-Tree is a balanced multi-way search tree.
Unlike a binary tree:
A / \
a B-Tree node can have many children.
Conceptually:
[20 | 40] / | \ <20 20-40 >40
B-Trees are designed particularly for storage systems where accessing memory/disk blocks is expensive.
26. B+ Tree
A B+ Tree is closely related to a B-Tree.
One important difference:
In a B+ Tree, actual records/data are generally stored in the leaf level, while internal nodes primarily guide searches.
Leaves are commonly linked:
[10,20] → [30,40] → [50,60] → [70,80]
This makes sequential/range access efficient.
B+ Trees are widely associated with:
- Database indexes
- File systems
- Storage systems
27. Suffix Array
Now we move into advanced string data structures.
A Suffix Array stores the starting positions of all suffixes of a string in sorted order.
For:
banana
suffixes are:
banana anana nana ana na a
Sorted:
a ana anana banana na nana
Their starting positions:
5 3 1 0 4 2
So the suffix array is:
[5, 3, 1, 0, 4, 2]
Suffix arrays are useful for:
- Pattern searching
- Longest repeated substring
- String comparison
- Longest common substring variants
- Advanced string problems
28. Suffix Tree
A Suffix Tree is a compressed Trie containing all suffixes of a string.
It can support many string operations very efficiently.
However, suffix trees are significantly more complicated to implement correctly than:
- Trie
- Suffix Array
For most DSA learning, understanding the concept is enough initially.
29. Treap
A Treap combines:
Tree + Heap
Each node has:
key priority
It maintains:
BST property on key + Heap property on priority
Example:
key = 50 priority = 10
Treaps are often randomized.
Expected operations:
Search → O(log n) Insert → O(log n) Delete → O(log n)
30. Skip List
A Skip List is a probabilistic alternative to balanced search trees.
Imagine multiple linked-list levels:
Level 3: 1 ------------------------ 20 Level 2: 1 -------- 10 ------------ 20 Level 1: 1 -- 5 -- 10 -- 15 ------ 20 Level 0: 1 -- 3 -- 5 -- 7 -- 10 -- 15 -- 20
Higher levels allow us to skip many elements.
Expected:
Search → O(log n) Insert → O(log n) Delete → O(log n)
31. Bloom Filter
A Bloom Filter is a probabilistic data structure for testing membership.
It answers:
"Is this element possibly present?"
It can say:
Definitely not present
or:
Possibly present
It can have false positives, but with the standard Bloom filter it does not have false negatives under normal operation.
Example:
Is username "uday123" already registered?
A Bloom filter can quickly say:
Definitely not
or:
Maybe
Then a database can perform the exact check if necessary.
32. Monotonic Stack
This is not a separate fundamental container like a tree, but it is an extremely important advanced problem-solving data structure technique.
A monotonic stack maintains elements in increasing or decreasing order.
For example:
[2, 1, 5, 3, 4]
Problems such as:
Find the next greater element.
For 2:
next greater = 5
For 1:
next greater = 5
For 5:
none
A monotonic stack can solve many such problems in:
O(n)
instead of O(n²).
33. Monotonic Queue
A monotonic deque is useful for problems such as:
Maximum value in every sliding window of size
k.
Example:
[1, 3, -1, -3, 5, 3, 6, 7]
For:
k = 3
we need:
3 3 5 5 6 7
A monotonic deque can solve this in:
O(n)
34. Advanced Data Structure Selection
This is very important.
Don't memorize structures randomly.
Think about the operation you need.
| Problem | Good Choice |
|---|---|
| Fast exact key lookup | Hash Table |
| Sorted key operations | BST / map |
| Prefix string search | Trie |
| Priority access | Heap |
| Range sum + updates | Fenwick Tree |
| Complex range queries | Segment Tree |
| Static range minimum | Sparse Table |
| Dynamic connectivity | DSU |
| MST with Kruskal | DSU |
| Database indexing | B/B+ Tree |
| Advanced string search | Suffix Array/Tree |
| Next greater element | Monotonic Stack |
| Sliding window maximum | Monotonic Deque |
| Probabilistic membership | Bloom Filter |
35. Segment Tree vs Fenwick vs Sparse Table
These three are commonly confused.
Fenwick Tree
Dynamic array + Prefix/range sum + Point update
Typical:
Update → O(log n) Query → O(log n)
Segment Tree
Dynamic array + Complex range queries + Updates
Typical:
Build → O(n) Query → O(log n) Update → O(log n)
Sparse Table
Static array + Repeated range queries
Typical RMQ:
Build → O(n log n) Query → O(1) Update → Not suitable
36. Advanced Data Structures and Complexity
A useful summary:
| Structure | Search/Query | Update |
|---|---|---|
| AVL | O(log n) | O(log n) |
| Red-Black | O(log n) | O(log n) |
| Segment Tree | O(log n) | O(log n) |
| Fenwick | O(log n) | O(log n) |
| DSU | ~O(1) amortized | ~O(1) amortized |
| Sparse Table | O(1)* | Not suitable |
| Treap | O(log n) expected | O(log n) expected |
| Skip List | O(log n) expected | O(log n) expected |
| Bloom Filter | O(k) | O(k) |
* For supported static queries such as RMQ with the appropriate preprocessing.
37. How Advanced Structures Connect to Your Previous Topics
You've already studied:
BST
Now:
BST ↓ AVL ↓ Red-Black Tree
These solve the problem of an unbalanced BST.
Arrays
Now:
Array ↓ Fenwick Tree Segment Tree Sparse Table
These solve repeated range-query/update problems.
Graphs
Now:
Graph ↓ DSU ↓ Kruskal
DSU helps efficiently manage connected components.
Strings
Now:
String ↓ Trie ↓ Suffix Array ↓ Suffix Tree
These handle increasingly advanced string-processing problems.
Stack / Queue
Now:
Stack ↓ Monotonic Stack Deque ↓ Monotonic Queue
These are powerful problem-solving patterns.
38. What Should You Learn First?
Don't try to master everything at once.
I recommend this order:
1. AVL Tree ↓ 2. Red-Black Tree concepts ↓ 3. Segment Tree ↓ 4. Fenwick Tree ↓ 5. DSU ↓ 6. Sparse Table ↓ 7. Monotonic Stack ↓ 8. Monotonic Queue ↓ 9. B-Tree / B+ Tree concepts ↓ 10. Suffix Array / Suffix Tree ↓ 11. Treap / Skip List ↓ 12. Bloom Filter
For interview and competitive-programming DSA, prioritize:
⭐⭐⭐⭐⭐ Segment Tree ⭐⭐⭐⭐⭐ DSU ⭐⭐⭐⭐⭐ Fenwick Tree ⭐⭐⭐⭐ Monotonic Stack ⭐⭐⭐⭐ Monotonic Queue ⭐⭐⭐⭐ AVL / Balanced BST concepts ⭐⭐⭐ Sparse Table ⭐⭐⭐ Suffix Array
39. Important Advanced DSA Pattern
A very important lesson is:
Advanced data structures are usually created to make a particular operation faster.
For example:
Normal Array ↓ Range Sum = O(n)
Add Fenwick Tree:
Range Sum = O(log n)
Or:
Normal BST ↓ Can become O(n)
Add balancing:
AVL / Red-Black ↓ O(log n)
Or:
Repeated graph connectivity ↓ Naive approach is expensive
Use:
DSU ↓ ~O(1) amortized
That's the mindset you should develop.
40. Final Mental Map
ADVANCED DATA STRUCTURES │ ┌──────────────────┼──────────────────┐ │ │ │ TREES RANGE GRAPH │ QUERIES CONNECTIVITY │ │ │ ┌────┴────┐ ┌─────┼─────┐ DSU │ │ │ │ │ AVL Red-Black Fenwick Segment Sparse Tree Tree Table │ Treap │ Skip List ┌───────────────────────────┐ │ STRINGS │ │ │ Trie Suffix Structures │ ┌──────┴──────┐ │ │ Suffix Array Suffix Tree ┌───────────────────────────┐ │ PROBLEM PATTERNS │ │ │ Monotonic Stack Monotonic Queue
Final Summary
Advanced Data Structures are specialized structures designed to efficiently solve problems that become expensive with basic arrays, lists, trees, or graphs.
The most important ones are:
Balanced Trees
- AVL Tree
- Red-Black Tree
- Treap
Range Query Structures
- Segment Tree
- Fenwick Tree
- Sparse Table
Graph/Connectivity
- Disjoint Set Union (DSU)
String Structures
- Suffix Array
- Suffix Tree
- Trie
Advanced Problem-Solving Structures
- Monotonic Stack
- Monotonic Queue
Storage/Systems
- B-Tree
- B+ Tree
- Bloom Filter
The key is not just remembering their names. For each structure, understand:
What problem does it solve? ↓ Why is the normal approach slow? ↓ How does the structure organize information? ↓ What operations does it make faster? ↓ What is the time/space complexity?