Daffodil International University

Faculty of Science and Information Technology => Science and Information => Topic started by: rashidacse on November 28, 2015, 12:51:05 PM

Title: What is a list of data structures that a competitive programmer must know?
Post by: rashidacse on November 28, 2015, 12:51:05 PM

Answer is different for different skill levels. I will try to categorize,

Beginner: Linked List, Stack, Queue, Binary Search Tree.
 
Intermediate: Heap, Priority Queue, Huffman Tree, Union Find, Tries, Hash Table, Tree Map.

Proficient: Segment Tree, Binary Indexed Tree, Suffix Array, Sparse Table, Lowest Common Ancestor, Range Tree.

Expert: Suffix Automaton, Suffix Tree, Heavy-Light Decomposition, Treap, Aho-Corasick, K-d tree, Link-Cut Tree, Splay Tree, Palindromic Tree, Rope,  Dancing Links, Radix Tree, Dynamic Suffix Array.

I have seen all of the listed data structures being used in various programming contests.

Many of them are given in language libraries. But it is very important to understand their dynamics. Otherwise understanding related higher level structures will be difficult (if possible