tom's blog

New data structures
By tom, 9 years ago, In English

Hello everyone,

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

Palindromic tree — http://adilet.org/blog/25-09-14/ ,
http://codeforces.net/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://codeforces.net/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

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

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

Thanks for collecting them!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A bit more about palindromic tree: link

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks, I'll update my post.

    → Reply
»
9 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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://codeforces.net/gym/100513/submission/8407367 :D

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

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,

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

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

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

We're waiting explanation from anta...

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

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.

→ Reply