What is a list of data structures that a competitive programmer must know?

Answer by Bidhan Roy:

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).

One may find some higher level data structures easier than lowers (happened to me).


Thanks for asking to answer.

What is a list of data structures that a competitive programmer must know?

Advertisements

Leave a comment

Filed under Life

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s