## 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?

Palindromic tree are very necessary.

Thank you.

IT'S A TRAP!!!

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.

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:

Sparse Table for static RMQ, preprocessing and

O(1) queryTreap for anything in

O(log_{2}(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 implementSegement Tree for

O(n) construction andO(log_{2}(n)) range queries and updatesFenwick 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

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))Heap for implementing Dijkstra, Queue for BFS and Stack for DFS and similar operations

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

Wavelet Tree for construction and fast rank queries in a range

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

Suffix array for many string problems

Link Cut Tree for maintaining dynamic trees