Nearly Tight Cell-Probe Lower Bounds for Querying on Tree via Talagrand InequalityResearch Paper
Succinct data structures store a combinatorial object in space close to the information-theoretic minimum while still answering queries quickly. Balanced parentheses are the basic case: an ordered tree with nodes, or a forest, is written as a word of brackets, and tree navigation reduces to bracket queries such as findclose (the position of the bracket…