Ugenz Academy/Tutorial

Advanceddatastructures

18 min read3,555 words

Reading progress

Keep learning

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 StructureMain Purpose
AVL TreeBalanced searching
Red-Black TreeBalanced searching
Segment TreeRange queries + updates
Fenwick TreePrefix/range sums + updates
DSUDynamic connectivity
Sparse TableFast static range queries
B-TreeDisk/database indexing
B+ TreeDatabase/file-system indexing
Suffix ArrayString processing
Suffix TreeAdvanced string processing
TreapRandomized balanced BST
Skip ListProbabilistic ordered structure
Bloom FilterFast probabilistic membership
Monotonic StackNext greater/smaller problems
Monotonic QueueSliding-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:

OperationComplexity
SearchO(log n)
InsertO(log n)
DeleteO(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:

  1. Every node is either red or black.
  2. The root is black.
  3. A red node cannot have a red child.
  4. Every path from a node to its relevant NIL leaves has the same number of black nodes.
  5. 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

FeatureAVLRed-Black
BalanceMore strictLess strict
SearchVery goodVery good
Insert/DeleteMore rotations possibleUsually fewer
HeightSmallerSlightly larger
Use caseSearch-heavyFrequent 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

FeatureSegment TreeFenwick Tree
Range sumYesYes
Point updateYesYes
Prefix sumYesYes
Range minimumYesNot as generally
Range maximumYesNot as generally
Complex operationsMore flexibleMore limited
MemoryO(n)O(n)
ImplementationMore complexSimpler

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.

ProblemGood Choice
Fast exact key lookupHash Table
Sorted key operationsBST / map
Prefix string searchTrie
Priority accessHeap
Range sum + updatesFenwick Tree
Complex range queriesSegment Tree
Static range minimumSparse Table
Dynamic connectivityDSU
MST with KruskalDSU
Database indexingB/B+ Tree
Advanced string searchSuffix Array/Tree
Next greater elementMonotonic Stack
Sliding window maximumMonotonic Deque
Probabilistic membershipBloom 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:

StructureSearch/QueryUpdate
AVLO(log n)O(log n)
Red-BlackO(log n)O(log n)
Segment TreeO(log n)O(log n)
FenwickO(log n)O(log n)
DSU~O(1) amortized~O(1) amortized
Sparse TableO(1)*Not suitable
TreapO(log n) expectedO(log n) expected
Skip ListO(log n) expectedO(log n) expected
Bloom FilterO(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?

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy