Nondeterministic BoundFor verify-sum queries implying the same bound, it would be shown that the lower bound for partial sums holds even for nondeterministic data structures.
A new version of Lemma, which bounds the entropy of (nondeterministic) queries in terms of the information transfer, is the only missing part of the proof.Data Structures Using Linear SpaceFor the longest common prefix of x and y, we write lcp(x, y) i.e. the largest i, such that the most significant i bits of x and y are same.On a set S = {y1… yn} the longest common prefix query is defined as:Lcp(x): returns some i ? n that maximizes lcp(x, yi).Since either the predecessor or the successor maximizes the common prefix, so it is immediate that predecessor search can solve lcp queries.
It yields that a reverse reduction also holds, and from now on we will only reason about lcp queries. (Notably this reduction is not needed in practice.To enjoy better constant factors, most lcp data structures can solve predecessor search with some ad hoc tweaks).Lemma Predecessor search can be solved with query time tq + O (1) and space S + O (n), if the lcp problem can be solved with query time tq and space S. Proof: Consider a binary tree of the root-to-leaf paths representing the values in S = {y1…yn} and depth w.
Among these n paths there are exactly n-1 branching nodes.There are two components in our data structure:All the branching nodes are stored in hash table, i.e.
pairs (l, v), where l is the depth of the node and v is the prefix leading to that node.Beginning with prefix v, we also store as associated data the minimum and maximum values in S.• We store a bit vector of size w (exactly a word) indicating which ancestors of x are branching nodes, for each yi?S.The query for the predecessor of x proceeds as follows:• Let i = LCP(x), run the LCP query.• Compute l = lcp(x, yi).• Below height l, find the highest branching node, v on the path yi.It can be done by examining the bit vector indicating the branching nodes above yi, because the bit vector is a word it takes constant time.• The maximum value under v (stored as associated data in the hash table) is the predecessor, if v is to the left of x.• The minimum value under v is the successor, and the predecessor is immediately before it in S, if v is to the right of x.
