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.