AmericanPsycho's blog

Data Structrues in competitive programming

By AmericanPsycho, history, 7 years ago, In English

Hi everyone

What data structures are needed in competitive programming?
I know all stl structures, segment tree and BIT. But I have heard
others like treap, AVL tree, persistents, but I don't know if those
structures are really neccesary for competitive programming or
all their uses can be replaced by others and if not,
What are all the necessary data structures?

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Palindromic tree are very necessary.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

In order to become "expert" , logic is most important , If we can not come up with the logic of problem then what is the importance of all these data structures.

→ Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it +26 Vote: I do not like it

I like data structures so, you don't need to learn each and every one of the following but I'll sort them by usefulness from my point of view:

  1. Sparse Table for static RMQ, preprocessing and O(1) query

  2. Treap for anything in O(log2(n)) like find, lower&upper bounds, split, join, erase, insert, order statistics, lazy range updates and queries. Actually any BST will do but treaps are my favourite as they are much easier to implement

  3. Segement Tree for O(n) construction and O(log2(n)) range queries and updates

  4. Fenwick Tree, like segment trees but has much smaller constant factors and hence they are much faster in practice but they are better suited for invertible operations like sum, xor, multiplication ... etc

  5. DSU: Disjoint Set Union aka Union-Find Performs fast set operations like maintaining a certain property for each disjoint set and joining two sets in O(α(n))

  6. Heap for implementing Dijkstra, Queue for BFS and Stack for DFS and similar operations

  7. Sqrt-Decomposition whether you consider it a data structure or a technique, it's still very effective for doing many peculiar operations in

  8. Wavelet Tree for construction and fast rank queries in a range

  9. Trie for string operations like searching and finding a prefix with certain property in time proportional to string length, it can do some interesting operations for integers using their binary representation

  10. Suffix array for many string problems

  11. Link Cut Tree for maintaining dynamic trees

→ Reply