### Ravenclaw_OIer's blog

By Ravenclaw_OIer, history, 5 months ago, ,

Sometimes data structures save the day — in China we have a saying that basically means "Data structures make up for dumbness". However, data structures differ vastly. Many of them are not only useful, but also, in some ways, beautiful.

I now ask the community: which one, do you think, is the most beautiful data structure? It can be very short but elegant, or very long but easy to understand, or simply come with a sense of harmony.

• +93

 » 5 months ago, # | ← Rev. 2 →   -51 Implementation
 » 5 months ago, # |   +55 BIT
 » 5 months ago, # | ← Rev. 2 →   +213 Personally, I think DSU(Disjoint Set Union) is very beautiful.It's very short, yet very efficient. It can maintain many things while being easy to understand. Its design is also very beautiful and harmonic.The main code of DSU can be expressed in two lines of code. However, it gives a near-linear complexity in maintaining the status of disjoint sets, which is simply amazing.My coach had once even composed a poem about DSU.
•  » » 5 months ago, # ^ |   +14 Can you share the poem?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +26 Sorry... I cannot find it now...But I do remember one line from it. His hand merges our disjoint skies. I'll try to find it!UPD Thanks to JT.AK.IOI! Solo at first, lonely trees cherish the ride.His hand merges our disjoint skies.Out of many is our root.Hands stretching, we seek our starry life.The paths are long, though recursing from The one.
•  » » » » 5 months ago, # ^ |   +12 Maybe you mean this Solo at first, lonely trees cherish the ride. His hand merges our disjoint skies. Out of many is our root. Hands stretching, we seek our starry life. The paths are long, though recursing from The one.
 » 5 months ago, # |   +72 Array, the best data structure of all times. It works very fast, easy to understand, solves a lot of problems, has advanced modifications like bitset and suffix array. Moreover, it can be used to implement segment trees, treaps and many more.
•  » » 5 months ago, # ^ |   +80 Agreed. It is the basis of nearly all advanced staff in algorithms. SpoilerBut arrays have an $O(n)$ complexity in random insert...
•  » » 5 months ago, # ^ |   +75 I like the integer data structure, nothing works without it.
•  » » » 5 months ago, # ^ |   +42 I like the electron data structure, nothing works without it.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +38 I like the quark data structure, nothing works without it.UPD. electrons doesn't contain quarks :(
•  » » » » » 5 months ago, # ^ |   +30 you played yourself
•  » » » » » » 5 months ago, # ^ |   +15 ... I'll make a particles theory where electrons are made of something.
•  » » » » » » » 5 months ago, # ^ |   +17 Eagerly awaiting riela's theory of everything
•  » » » » » » » » 5 months ago, # ^ |   +3 The theory of everything is too hard for physicists, we sps should do it.
•  » » » » » » » » » 5 months ago, # ^ |   0 Can I be your co-author?
•  » » » » » » » » » 5 months ago, # ^ |   0 are you well versed in QM and GR?
•  » » » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 I'm well versed in SP
•  » » » » » » » » » 5 months ago, # ^ |   0 Soon I'll start the future gadgets lab. You can try to join, there will be an entrance exam (sp contest)
•  » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +2 Electron is a string
•  » » » » » » » » 5 months ago, # ^ |   +10 and what is a char?
•  » » » » » » » » » 5 months ago, # ^ |   +2 Python: Char?
•  » » » 5 months ago, # ^ | ← Rev. 5 →   -18 I thought we are talking about algorithmic data structure which we can write on editor.
 » 5 months ago, # |   +40 Cartesian Tree
 » 5 months ago, # |   +10 Heavy light decomposition. It allows you to solve basically any problem where you make some updates/queries on tree in nlogn time. Although it's difficult to code it, the idea is really simple and anybody who's ever heard about segment trees will be able to understand it.
•  » » 5 months ago, # ^ |   +17 It's not difficult to code if you make it right:)
•  » » » 5 months ago, # ^ |   0 By difficulty I mean that the code is rather long so it's easy to make mistake while coding, especially when you use iterative segment tree.
•  » » » » 5 months ago, # ^ |   0 The code for HLD itself is pretty short.
•  » » » » » 5 months ago, # ^ |   0 Agree, but every HLD uses some kind of segment trees and those two combined together can get a little bit messy. Still, I'd love to see your implementation for HLD itself.
•  » » » » » » 5 months ago, # ^ |   0 57767880: everything is nicely separated, so you have a segment tree (optimised to be pretty fast), query/update functions, a DFS_construct() call that builds the HLD and then separately filling the segment trees over paths in the constructor.DFS_construct computes everything you could possibly need, including preorder renumbering of vertices and the corresponding intervals, the reverse of this renumbering, explicit paths as arrays of vertices, the (path, position in it) pairs for each vertex, depths of all vertices (in a segment tree), subtree sizes, parents and sons. Less than 30 lines.
•  » » 5 months ago, # ^ |   -7 HLD doesn't work very well for problems with subtree queries I think. It is more suited for handling path queries.
•  » » » 5 months ago, # ^ |   +45 It's not hard to build HLD not only for path queries but also for subtree queries
•  » » » » 5 months ago, # ^ |   0 Sorry for the misunderstanding. I meant to say that one doesn't use HLD to compute subtree queries, because HLD merely optimizes path queries in a tree. Of course, we could build a data structure in a way that it supports both subtree and path queries. But the chains that are built from the HLD preprocessing are only useful for querying over paths.
•  » » » » » 5 months ago, # ^ |   +8 If you make every heavy edge first, after running the Euler tour on the tree each heavy path (and subtree) becomes a continuous segment. You can handle all the operations in a single segment tree!
•  » » » » » » 5 months ago, # ^ | ← Rev. 5 →   0 Well. That's true but HLD doesn't make your subtree queries any more optimal I think. Whereas it optimizes path queries greatly. For example, given a problem which only requires subtree queries, say find the sum of values in a subtree where values are tagged to every vertex. I don't think HLD will help in the time complexity. But in the case where we have both subtree and path queries, while HLD won't really help us in optimizing the complexity of the subtree queries, storing data in the way you described will simplify our implementation of course.
•  » » » 5 months ago, # ^ |   +17 Here you go: Easiest HLD with subtree queries
•  » » » 5 months ago, # ^ |   +2 Guys, here he comes up again with yet another non trivial idea to get downvotes.
 » 5 months ago, # |   +30 treap.
 » 5 months ago, # |   0 Segment tree with treap on each node
 » 5 months ago, # |   +71 HLD with persistent compressed treaps on paths :)
 » 5 months ago, # |   0 Merge Sort Tree
 » 5 months ago, # |   +17 Sparce Table
 » 5 months ago, # |   0 std::vector< vector< vector > >
 » 5 months ago, # |   0 array
 » 5 months ago, # |   0 splay
 » 5 months ago, # |   0 Adjacency list
 » 5 months ago, # |   +83 splay trees with treaps on each node which is used to get lines from convexhull trick with heavy light decomposition and suffix tree on each line.
•  » » 5 months ago, # ^ |   +9 would you PLEASE publish the implementation of that data structure?
 » 5 months ago, # | ← Rev. 2 →   -9 Chtholly Tree? It's elegantlly brute.Though not admitted by academic organizations.
•  » » 5 months ago, # ^ |   -6 You can't even spell it correctly, it is "Chtholly Tree"
•  » » » 5 months ago, # ^ |   -14 That's my mistake.But it's the data structure that counts.
 » 5 months ago, # |   0 Voronoi Diagram.
 » 5 months ago, # |   +49 when you make a segtree with treaps in each node, and compressing straight chains in the segtree, and making the whole structure persistant : whoa. utterly useless.
 » 5 months ago, # |   +32 int
•  » » 5 months ago, # ^ |   +16 int128_t
 » 5 months ago, # |   +8 Wavelet matrices. For each bit position in an array, count the ones and stable partition on that. Then you can answer queries for counting elements in any range in any subarray and also queries for the kth smallest element.
 » 5 months ago, # |   +5 sqrt decomposition and BIT
 » 5 months ago, # | ← Rev. 2 →   0 TreeMap and TreeSet for Java ;)
 » 5 months ago, # |   +13 Link/Cut Tree
 » 5 months ago, # |   -28 I think all the data structures are rubbish. Why are they useful? What can we do with them? Nothing.
 » 5 months ago, # |   +35 Obviously palidromic tree.
 » 5 months ago, # |   +3 I think RB-Tree is the most beautiful data structure because it's colorful and useful :D
 » 5 months ago, # |   +1 ODT(OldDriverTree)If you don't know what's ODT,you can see it in this problem
•  » » 5 months ago, # ^ |   +11 Unfortunately some newbies (in Chinese I actually want to say “小鬼”) are trying to solve every data structure problem with ODT and keep getting TLE. When I try to tell them their solution is slower than $O(n^2)$ in worst case they just ignore me and do some stupid tweaking in their program. Of course those tweaking don't work.That's really wasting time.
• »
»
»
5 months ago, # ^ |
Rev. 3   +11

Although Chtholly Tree can solve nearly everything, its efficiency depends heavily on the randomness of test sets. The problem setters can easily hack it by making no modification operations.

However, in multi-test-case contests like CNOI, not all test case can hack Chtholly Tree, and it can easily gain points. It is way easier to code than other data structures after all.

These newbies do not actually understand it and are just using it to show off, I believe. A true coder who wishes to get high marks may learn it but not try to use it to solve everything.

UPDATE: Here is what I found on USACO Training.

### Things to Avoid: Coolness Factor

Try not to fall into the "coolness" trap. You may have just seen the neatest data structure, but remember:

• Cool ideas that don't work aren't.
• Cool ideas that'll take forever to code aren't, either

It's much more important that your data structure and program work than how impressive your data structure is.

 » 5 months ago, # |   -16 Pair (; 8===э
 » 5 months ago, # | ← Rev. 2 →   0 And I think the block(分块) is beautiful too.Althougth it's cost sqrt(n) (longer than log(n) )，it's very easy too understand and it can solve a lot of data structure problems
•  » » 5 months ago, # ^ |   +3 Hey guy,beaatiful(滑稽
•  » » » 5 months ago, # ^ |   +3 It's a mistake
•  » » » » 5 months ago, # ^ |   +1 2333333
 » 5 months ago, # |   +31 bitset :)
 » 5 months ago, # |   0 Although not as used as other popular data structures, trie seems to me as a beautiful data structure along with the persistency added into it if required .
 » 5 months ago, # |   0
 » 5 months ago, # | ← Rev. 3 →   -24 f
 » 5 months ago, # |   0 ODT tree,segment tree,Balanced binary tree:)
 » 5 months ago, # |   0 Heap
 » 5 months ago, # |   0 Implicit treap
 » 5 months ago, # |   +6 Persistent 2-3 tree
 » 5 months ago, # | ← Rev. 2 →   +11 stack, it helps in solving some hard problem with ease without using some other complex fancy data structures, well this is what I think.
 » 5 months ago, # |   +3 Sparse Table
 » 5 months ago, # |   +39 Suffix automaton. Very easy to code (around 20 lines) but solves many difficult string problems.
 » 5 months ago, # |   +5 Randomized data structures such as skip lists.
 » 5 months ago, # |   0 treap
 » 5 months ago, # |   0 Bloom Filter
 » 5 months ago, # |   +79 Human brain. It is used to store info about other data structures and can apply them to a problem.(My brain does that pretty fast. Just $O(n^n)$!)
 » 5 months ago, # |   -8 Quoting Brian Kernighan : "If you would have to choose to teach one data structure and one data structure only, you should choose the hash table. Every other DS is a derivative."So yeah, unordered sets rock.
•  » » 5 months ago, # ^ |   +59 I'm struggling to understand how any data structure is a derivative of the hash table. Okay, other hash-based things like Bloom filters are, but none of the tree-based things or stuff like suffix automata are.Also hash tables may work very well, but IMO they are far from "beautiful".
•  » » » 5 months ago, # ^ |   0 Honestly I'm struggling too :P, and I'm not really sure I have correctly interpreted what he has stated here https://m.youtube.com/watch?v=Sg4U4r_AgJU&t=24m50s .Regardless I think he is referring to the fact that almost always you can efficiently solve a given problem with an associative array/hash table, instead of another non-linear data structure like a red-black tree or a Fenwick tree, exploiting the O(1) search insert and delete time.
•  » » » » 5 months ago, # ^ |   +9 exploiting the O(1) search insert and delete time.It is compulsory to mention that the O(1) time complexity is only amortised (i.e. A single operation on the hash table could be very expensive but in the long run, the cost is amortised constant. Why is it important to make this distinction? Well, let's say that you are building a real-time system, a data structure that gives you amortised complexity may not be so practical because the system may not respond quickly at critical moments.)
•  » » » » » 5 months ago, # ^ |   +1 Well, that's very nice to know !! :] Damn, I didn't knew about amortized analysis until now, thanks.
•  » » » » » » 5 months ago, # ^ |   +6 I didn't knew about amortized analysis until nowWell. Hashing is taught in every introductory Data Structures course and its amortized complexity is very likely to be mentioned. If you really want to learn how these data structures work, study formal academic material (e.g. those from opencourseware). Don't learn from some CP site/blog as it often omits important details. On the other hand, CP sites are good for learning about unorthodox optimization tricks which you won't learn in academia. So pick the correct site to learn the correct thing.
•  » » » » » » » 5 months ago, # ^ |   0 Well thanks again :) .To be honest, I was learning DS using "Competitive Programming Book 3", though the latter skips various fundamental topics in computer science, because the author assumes the reader already knows them. So yeah, I guess I'll give opencourseware a shot or two. I hope your comments will get seen by others who are struggling with CP as well.
 » 5 months ago, # |   0 SAM,of course
 » 5 months ago, # | ← Rev. 2 →   +30 Fenwick tree (sadly, it seems that it was not mentioned here). This data structure is easy to code, but powerful. It still looks like magic for me :)Also, I like Sqrt-tree (the idea of putting sqrt-decompositions inside each other is beautiful, and yes, I like this data structure, because I invented it) :)
•  » » 5 months ago, # ^ |   +8 Fenwick tree was mentioned in the second comment.
 » 5 months ago, # |   0 Treap and SQRT-Decomposition
 » 5 months ago, # |   +6 pbds
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 That's easy to use but I can't agree it is "beautiful". The code quality is questionable because lack of maintainance. For example, a stupid bug had been there since 2011 until I fixed it in 2017!And now Jonathan wants to remove it from libstdc++ because there are no maintainers and only a little users (all from competitive programming).
 » 5 months ago, # |   +4 Array, according to me, is the best data structure.
 » 5 months ago, # |   0 suffix array is easy to understand and beautiful idea of sort technique
 » 5 months ago, # |   +3 fhq treap, which only uses two kinds of operation: split and merge, can be an alternative for splay in most cases(exceptions: LCT) and can be persistent. It's beautiful because of its short code and easy operations.
 » 5 months ago, # | ← Rev. 2 →   +1 Persistent Treap(FHQ treap)It can solve sequence problems that Splay can solve(Except Link-Cut Tree).The implementation is more straightfoward than Splay.All you need is to write two functions merge(x,y)andsplit(rt,k).Then combine these two to write insertanddelete.
•  » » 5 months ago, # ^ |   0 Lefist Tree is also an elegant data structure. Why nobody mentioned it in this post?
 » 5 months ago, # |   +8 My favourite data structures are Link-Cut Cactuses and Heavy-Light Decomposition on the Cactus.
 » 5 months ago, # |   +8 How about compressed $0/1$ trie? It runs much faster than a balanced tree, and it can do almost everything a balanced tree can do! Also it can be easily used in xor problems. I learned the beautiful DS from Xiuhan Wang, who won Silver Medal in IOI 2019.
 » 5 months ago, # |   +29 Li Chao Tree. This is an data structure that can add line in 2D plane, and also can find the minimum y-value when $x=a$. You can use set+ConvexHullTrick to solve this problem, but with Li Chao Tree, you can also add segments. Although this fact, implementation is not so heavy, like RMQ. That’s why I think this data structure is beautiful.
 » 5 months ago, # |   +40 Black hole — Insertion is easy. Retrieval is difficult though.
•  » » 5 months ago, # ^ |   0 Unfortunately, the time-space are so distorted near the black hole so in your point of view the "insertion" will take infinite time (assuming you're not in the black hole). So you have an $O(\infty)$ insertion! :)
 » 5 months ago, # |   +2 Trie ! It comes under advance data structure but actually is very easy to understand and implement. And the concept behind it is exceptionally beautiful. The time complexity reduces by a great extent too.
 » 5 months ago, # |   0 Tango tree
 » 5 months ago, # |   0 I like map data structure quite useful in various areas.
 » 5 months ago, # |   0 sqrt decomposition
 » 5 months ago, # |   0 Segment tree is a very powerful data structure, it can be used in many problem for update and query both point update/query ans range update/query. It can also be used in many tree problems for update and queries.
 » 4 months ago, # |   +8 I think it is a binary indexed tree (Fenwick tree). It is very easy and fast to code. Also, the idea of a Fenwick tree is very beautiful.
 » 4 months ago, # | ← Rev. 3 →   -13 The most beautiful (and useful) data structure is the human brain. It allows us to answer a superset of problems solvable by any DS in Competitive Programming (by simply knowing which DS to use). Too bad, many greens, grays and cyans don't know how to use this data structure.
•  » » 4 months ago, # ^ |   +20 How does this beautiful data structure allow you to leave such offensive comments?
•  » » » 4 months ago, # ^ | ← Rev. 3 →   +7 Because this beautiful data structure allows one to post shitty blogs and post shitty comments which often can be answered by a Google search/being more hardworking.
 » 2 months ago, # | ← Rev. 2 →   0 SPARSE TABLE
 » 3 weeks ago, # |   0 Array because thats the only DS I know
 » 2 weeks ago, # |   +8 Sparse Table))
 » 13 days ago, # |   +9 Well, i think its segment tree ! It is used alot and it is enjoyable to use it!
 » 13 days ago, # |   +8 vector
 » 13 days ago, # |   0 2D persistent segment tree.ask lots of things about any time ;)
 » 13 days ago, # |   +21 Segment tree :D especially when you use it with HLD.