19. Advanced Data Structures

19.1 Trie (Prefix Tree)

A Trie is a tree‑based structure where each node represents a character and the path from the root to a node spells a prefix of one or more stored strings. It excels at prefix‑based queries.

Node Structure

• children[alphabetSize] – array or map of child pointers (one per possible character).
• boolean endOfWord – true if a word terminates at this node.

Operations

1. Insert(word) – traverse/create nodes for each character; O(L) where L = word length.
2. Search(word) – follow the path; return endOfWord at the final node; O(L).
3. StartsWith(prefix) – similar to search but only need to reach the prefix node; O(L).

Complexity Summary

Example

Inserting "cat", "car", "dog" yields:

root
 ├─ c ─► a ─► t (endOfWord)
 │          └─► r (endOfWord)
 └─ d ─► o ─► g (endOfWord)

Applications

• Autocomplete systems.
• Spell checkers.
• IP routing (longest prefix match).
• Binary try for bitwise operations.

19.2 Segment Tree

A Segment Tree is a binary tree that stores aggregated information (sum, min, max, GCD, etc.) for intervals of an array, enabling logarithmic‑time range queries and point updates.

Node Fields

• interval [l, r] – the segment this node represents.
• value – aggregated result for the interval (e.g., sum).
• Optional lazy fields for range updates.

Core Operations

1. Build – recursive construction from leaves; O(n).
2. Query(l, r) – recursively combine nodes covering [l, r]; O(log n).
3. Update(pos, val) – point update, then recompute ancestors; O(log n).
4. Range Update (with lazy) – store pending operation, push down when needed; O(log n) amortized.

Complexity Summary

Example – Sum Segment Tree

Array: [1, 3, 5, 7, 9, 11]

Query sum on interval [2,5] (0‑based) → elements 5,7,9,11 sum = 32.

Update position 3 to value 4 → new array [1,3,5,4,9,11]; internal nodes are recomputed accordingly.

Applications

• Range sum/min/max queries.
• Dynamic order statistics.
• Geometric problems (e.g., counting points in a rectangle).
• With lazy propagation: range add/assign, range increment.

19.3 Fenwick Tree (Binary Indexed Tree – BIT)

The Fenwick Tree (or BIT) is a compact structure for maintaining prefix sums and supporting point updates in O(log n) time, using only an array of size n+1.

Internal Representation

Array BIT[1..n] where each entry stores the sum of a sub‑range:

where lowbit(x) = x & -x isolates the lowest set bit.

Operations

1. update(i, delta) – add delta to position i and propagate upward:

   while i ≤ n:
       BIT[i] += delta
       i += lowbit(i)
   
   

2. query(i) – prefix sum [1..i]:

   res = 0
   while i > 0:
       res += BIT[i]
       i -= lowbit(i)
   return res
   
   

3. rangeQuery(l, r) – query(r) - query(l-1).

Complexity Summary

Example

Using the same array [1,3,5,7,9,11] (1‑based indexing):

• After building, query(4) returns 1+3+5+7 = 16.
• Range sum [2,5] = query(5) - query(1) = (1+3+5+7+9) - 1 = 24.
• Update position 3 by +2 (value 5 → 7): propagate to BIT indices 3,4,8…; subsequent queries reflect the change.

Applications

• Prefix sum queries with frequent point updates.
• Counting inversions (via coordinate compression).
• Binary indexed tree of frequencies for order statistics.
• Foundation for more complex structures like 2‑D BIT.

19.4 Disjoint Set Union (DSU / Union‑Find)

Disjoint Set Union maintains a collection of disjoint sets, supporting union (merge two sets) and find (identify the representative of a set). With heuristics it achieves practically constant amortized time.

Heuristics

• Path Compression – during find(x), make every visited node point directly to the root.
• Union by Rank / Size – attach the root of the smaller tree under the root of the larger tree (rank ≈ height, size ≈ number of elements).

Pseudo‑code

function find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   // path compression
    return parent[x]

function union(a, b):
    ra = find(a); rb = find(b)
    if ra == rb: return
    // union by size
    if size[ra] < size[rb]:
        swap(ra, rb)
    parent[rb] = ra
    size[ra] += size[rb]

Complexity Summary

With both heuristics, the amortized time per operation is O(α(n)), where α is the inverse Ackermann function (≤ 5 for all practical n).

Example

Perform:

• union(1,2) → set {1,2}
• union(2,3) → set {1,2,3}
• union(4,5) → set {4,5}
• find(3) → returns root of {1,2,3} (say 1).

Applications

• Kruskal’s Minimum Spanning Tree.
• Percolation theory.
• Dynamic connectivity in graphs.
• Image segmentation (union of neighboring pixels).
• Offline connectivity queries.

19.5 Bloom Filter

A Bloom Filter is a probabilistic data structure that tests set membership. It guarantees no false negatives but may yield false positives.

Structure

• Bit array of m bits, all initially 0.
• k independent hash functions h₁ … h_k mapping items to positions in [0, m‑1].

Operations

1. Insert(x) – for each i in 1..k set BIT[h_i(x)] = 1.
2. Query(x) – return true iff all k bits are set; otherwise false (definitely not in set).

False Positive Probability

After inserting n elements, the probability that a particular bit is still 0 is:

Thus the probability that all k bits are 1 (false positive) is approximately:

The optimal number of hash functions minimizing this probability is:

Example

Let m = 64 bits, k = 3 hash functions, n = 10 inserted items.

• Expected false positive ≈ (1 - e^{-3·10/64})^3 ≈ 0.02 (2%).

Applications

• Web caches – avoid expensive lookups for non‑existent keys.
• Database systems – skip disk reads for absent rows.
• Network routers – fast IP blacklist checking.
• Counting variants (e.g., Counting Bloom Filter).

19.6 Skip List

A Skip List is a probabilistic balanced linked list that provides O(log n) expected time for search, insertion, and deletion, while being simpler to implement than balanced trees.

Structure

• Each element appears in a sorted linked list at the base level (level 0).
• With probability p (commonly 0.5) an element is promoted to the next higher level, forming a tower of nodes.
• The highest level contains O(log_{1/p} n) nodes in expectation.
• Each node stores key, value, and an array forward[level] of pointers to the next node at each level.

Search Algorithm

1. Start at the highest level, leftmost header.
2. Move right while the next node’s key < target.
3. When cannot move right, drop down one level.
4. Repeat until level 0; if the next node’s key equals target, return it.

Insert / Delete

Follow the search path to locate the insertion point. Create a new node with a random height determined by flipping a coin until a failure (or reaching a max height). For each level ≤ node.height, insert the node by updating the forward pointers of the predecessors collected during the search. Deletion is symmetric: remove the node from each level where it appears.

Complexity Summary (Expected)

Example

Inserting keys [3,6,7,9,12,19,17,26,21,25] with promotion probability 0.5 yields an expected height of about ⌈log₂ 10⌉ = 4. A possible tower configuration (illustrated in text) might be:

Level 3: -∞ --------------------> +∞
Level 2: -∞ -----> 9 ----------> +∞
Level 1: -∞ -> 6 ----> 12 ----> 19 --> 26 -> +∞
Level 0: -∞ -> 3 -> 6 -> 7 -> 9 ->12->17->19->21->25->26-> +∞

Searching for key 21 starts at level 3, moves right to +∞ (too big), drops to level 2, moves to 9, then to +∞ (drop), level 1: 12 → 19 → +∞ (drop), level 0: 19 → 21 (found).

Applications

• Alternative to AVL/Red‑Black trees when simplicity matters.
• Concurrent data structures – lock‑free skip lists are easier to reason about.
• Memory‑efficient ordered maps in languages lacking built‑in balanced trees.
• Indexing in databases and file systems.

All structures discussed herein complement the basic arrays, linked lists, stacks, queues, and trees covered earlier in the course. Mastery of these advanced tools enables tackling a wide range of algorithmic challenges with optimal asymptotic performance.