I've found couple of interesting data structures recently, e.g:
and Wavelet Matrix — http://www.dcc.uchile.cl/~gnavarro/ps/spire12.4.pdf (anta used it in problem E in last round — http://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.