Hello everyone,

I've found couple of interesting data structures recently, e.g:

Palindromic tree — http://adilet.org/blog/25-09-14/ ,

http://mirror.codeforces.com/blog/entry/13959 (thanks to adamant)

and Wavelet Matrix — http://www.dcc.uchile.cl/~gnavarro/ps/spire12.4.pdf (anta used it in problem E in last round — http://mirror.codeforces.com/contest/543/submission/11036065 )

It made me wonder, how many great and useful, less known data structures are out there?

This is a question for you — do you know any?

Please share them with us.

Greetings

Thanks for collecting them!

I will hate Codeforces community! Why do I get downvote because of the previous comment? //fixed typo@2015.5.12

Wow,Guess now I know

A bit more about palindromic tree: link

Thanks, I'll update my post.

I think that this Wavelet Matrix is not the only data structure you can encounter in anta's codes :D. His library is truly astonishing. Check this code: http://mirror.codeforces.com/gym/100513/submission/8407367 :D

Can't view the code sadly, I suppose I have neither solved the problem nor am I high yellow/red.

Hm, probably it's visible to people with coach mode one. Here it is: http://ideone.com/xVBc3S

Anyone can explain how the Wavelet tree is being used in https://www.codechef.com/AUG15/problems/DISTNUM ? From anta's code it seems like it is indeed what is being used,

Will be great if the structures will be added on e-maxx.

We're waiting explanation from anta...

The data structure that I called "Wavelet Matrix/Tree" is not the true Wavelet Matrix/Tree because that is not succinct.

Basically, the data structure is a kind of implementation of range tree. It is maybe faster than usual implementation I believe.