News:

Daffodil International University Forum contains information about Open Text material, which is only intended for the significant learning purposes of the university students, faculty, other members, and the knowledge seekers of the entire world and is hoped that the offerings will aide in the distribution of reliable information and data relating to the many areas of knowledge.

Main Menu

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

Started by rashidacse, November 28, 2015, 12:51:05 PM

Previous topic - Next topic
Print
Go Down Pages1
User actions

rashidacse

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
Print
Go Up Pages1
User actions