<p>This is similar to a log-structured merge trees or <a href="http://supertech.csail.mit.edu/papers/sbtree.pdf">cache oblivious lookahead arrays</a> (or COLAs). </p>

<p>The simplest COLA is an array of size $2^k-1$ with virtual "levels" of length $2^i$ for $0 \leq i &lt; k$ laid out in order in the array. Each level is totally full or totally empty, and each level is sorted.</p>

<p>To insert an item, place it it level 0 (with $2^0$ length) if level 0 is empty. Otherwise, merge it with the item at level 0 and fill level 1 (with $2^1$ length) with the resulting list of length 2. If level 1 is already full, merge again; repeat.</p>

<p>Insert takes $O(\lg n)$ amortized / $O(n)$ worst-case time. Lookup takes $O(\lg^2 n)$ time. More advanced versions can reduce and partially deamortize these.</p>

CC BY-SA 3.0
2011-08-06T16:50:31.447Z
2011-08-06T17:36:52.750Z
2011-08-06T17:36:52.750Z
jbapple
<p>You're describing the classical <a href="http://dx.doi.org/10.1016/0196-6774(80)90015-2">Bentley-Saxe logarithmic method</a>, applied to static sorted arrays.  The same idea can be used to add support for insertions to any static data structure (no insertions or deletions) for any decomposable searching problem.  (A search problem is <em>decomposable</em> if the answer for any union $A\cup B$ can be computed easily from the answers for the sets $A$ and $B$.)  The transformation increases the amortized query time by a factor of $O(\log n)$ (unless it was already bigger than some polynomial in $n$), but increases the space by only a constant factor.  Yes, it can be deamortized, thanks to Overmars and van Leeuwen, but you really don't want to do that if you don't have to.</p>

<p><a href="http://compgeom.cs.uiuc.edu/~jeffe/teaching/datastructures/notes/01-statictodynamic.pdf">These notes</a> cover the basics.</p>

<p>Cache-oblivious lookahead arrays are the mutant offspring of Bentley-Saxe and van Emde Boas trees on steroids.</p>

CC BY-SA 3.0
2011-08-06T22:04:16.140Z
Those are beautifully written and illustrated notes, and I have used them as a reference many times. Thanks for making them available!
jbapple
CC BY-SA 3.0
2011-08-06T22:07:00.427Z
I see how shuttle trees (from the first half of the paper introducing cache oblivious lookahead arrays) are related to vEB trees, but what is the relationship between COLAs and vEB trees?
jbapple
CC BY-SA 3.0
2011-08-07T07:27:45.167Z
Thanks, this material seems a very interesting generalization of the idea. I have always thought that data structures are frozen algorithms, which you can run step by step, but I had never found a useful formalization of that intuition.
pbaren
CC BY-SA 3.0
2012-03-05T17:05:13.470Z
Did the first link work for anyone else?
A T
CC BY-SA 3.0
2012-03-05T20:31:19.290Z
Yes, I just tried it.  (Unfortunately, it goes to an Elsevier paywall; sorry!)
Jeffε
CC BY-SA 4.0
2018-11-26T18:11:24.023Z
The link to the note breaks and probably should be replaced by http://jeffe.cs.illinois.edu/teaching/datastructures/notes/01-statictodynamic.pdf
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-08-06T18:41:18.780Z
2011-08-06T18:41:18.780Z
Jeffε
<p>I haven't managed to find this data structure, but I'm not an expert in the field.</p>

<p>The structure implements a set, and is basically an array of comparable elements with an invariant. The invariant is the following (defined recursively):</p>

<p>An array of length 1 is a merge-array.</p>

<p>An array of length 2^n (for n > 0) is a merge-array iff:</p>

<ul>
<li>the first half is a merge-array and the second half is empty
or</li>
<li>the first array is full and sorted, and the second half is a merge-array.</li>
</ul>

<p>Note that if the array is full, it is sorted.</p>

<p>To insert an element, we have two cases:</p>

<ul>
<li>If the first half is not full, insert recursively in the first half.</li>
<li>If the first half is full, insert recursively in the second half.</li>
<li>After the recursive step, if the whole array is full, merge the
halves (which are sorted), and resize it to the double of its original
length.</li>
</ul>

<p>To find an element, recurse in both halves, using binary search
when the array is full. (This should be efficient since there are
at most $O(\log(n))$ ascending fragments).</p>

<p>The structure can be thought as a static version of mergesort.</p>

<p>It's not clear what one should do to erase an element.</p>

<p>Edit: after improving my understanding of the structure.</p>

CC BY-SA 3.0
2011-08-06T16:12:54.690Z
You defined it, therefore it exists. I think you have to smooth out some points, though. First, invariant #2 confuses me as it does does not seem to apply to intermediate states as you describe them. Second, what do you do when elements are removed?
Raphael
CC BY-SA 3.0
2011-08-07T07:13:42.000Z
You dreamt *up* a data structure, not dreamt of it...
Andrej Bauer
CC BY-SA 3.0
2011-08-07T07:22:03.300Z
@Raphael Thanks for your comments, I improved the definition following your thoughts. I didn't think of an algorithm for removal, I just wanted to check if this structure was in the literature before dedicating more time to it (and couldn't find anything in Google). On your first sentence, you can define God, but does it exist? :)
pbaren
CC BY-SA 3.0
2011-08-07T07:23:07.400Z
@Andrej Thanks, English is not my native language. (I guess it's not yours either :)
pbaren
CC BY-SA 3.0
2011-08-07T10:10:30.550Z
This is just a dictionary speaking through me.
Andrej Bauer
CC BY-SA 3.0
2011-08-07T10:27:59.260Z
@pbaren: Once you define the "God" the abstract concept exists, sure. While such is all we need in case of data structures, you would want a little more to really say "God exists", wouldn't you? But, see [this question](http://cstheory.stackexchange.com/questions/1977/false-proof-for-computability-of-a-function).
Raphael
CC BY-SA 3.0
2011-08-07T18:57:38.870Z
@Andrej: the OP originally had "dreamt _with_", which is almost certainly not what was meant.  I changed it to "of" instead of "up".  Both are correct grammatically, but both also change the meaning.  "Of" was the more interesting sounding option...
András Salamon
CC BY-SA 3.0
2011-08-08T07:23:27.513Z
I agree it is definitely the more interesting choice. I often dream up mathematical objects but rarely do I dream of them.
Andrej Bauer
<ds.data-structures>
I dreamt of a data structure, does it exist?
pbaren
# I dreamt of a data structure, does it exist?

(Asked by: username_0 on 2011-08-06)

I haven't managed to find this data structure, but I'm not an expert in the field.

The structure implements a set, and is basically an array of comparable elements with an invariant. The invariant is the following (defined recursively):

An array of length 1 is a merge-array.

An array of length 2^n (for n > 0) is a merge-array iff:

* the first half is a merge-array and the second half is empty
  or
* the first array is full and sorted, and the second half is a merge-array.

Note that if the array is full, it is sorted.

To insert an element, we have two cases:

* If the first half is not full, insert recursively in the first half.
* If the first half is full, insert recursively in the second half.
* After the recursive step, if the whole array is full, merge the
  halves (which are sorted), and resize it to the double of its original
  length.

To find an element, recurse in both halves, using binary search
when the array is full. (This should be efficient since there are
at most $O(\log(n))$ ascending fragments).

The structure can be thought as a static version of mergesort.

It's not clear what one should do to erase an element.

Edit: after improving my understanding of the structure.

**Tags:** ds.data-structures

> **Comments:**
> **username_1**: You defined it, therefore it exists. I think you have to smooth out some points, though. First, invariant #2 confuses me as it does does not seem to apply to intermediate states as you describe them. Second, what do you do when elements are removed?  
> **username_2**: You dreamt *up* a data structure, not dreamt of it...  
> **username_0**: @username_1 Thanks for your comments, I improved the definition following your thoughts. I didn't think of an algorithm for removal, I just wanted to check if this structure was in the literature before dedicating more time to it (and couldn't find anything in Google). On your first sentence, you can define God, but does it exist? :)  
> **username_0**: @Andrej Thanks, English is not my native language. (I guess it's not yours either :)  
> **username_2**: This is just a dictionary speaking through me.  
> **username_1**: @username_0: Once you define the "God" the abstract concept exists, sure. While such is all we need in case of data structures, you would want a little more to really say "God exists", wouldn't you? But, see [this question](http://cstheory.stackexchange.com/questions/1977/false-proof-for-computability-of-a-function).  
> **username_3**: @Andrej: the OP originally had "dreamt _with_", which is almost certainly not what was meant.  I changed it to "of" instead of "up".  Both are correct grammatically, but both also change the meaning.  "Of" was the more interesting sounding option...  
> **username_2**: I agree it is definitely the more interesting choice. I often dream up mathematical objects but rarely do I dream of them.  

---

## 2 answers

### Answer by username_5 on 2011-08-06. Score: 31 | Accepted answer

You're describing the classical [Bentley-Saxe logarithmic method](http://dx.doi.org/10.1016/0196-6774(80)90015-2), applied to static sorted arrays. The same idea can be used to add support for insertions to any static data structure (no insertions or deletions) for any decomposable searching problem. (A search problem is *decomposable* if the answer for any union $A\cup B$ can be computed easily from the answers for the sets $A$ and $B$.) The transformation increases the amortized query time by a factor of $O(\log n)$ (unless it was already bigger than some polynomial in $n$), but increases the space by only a constant factor. Yes, it can be deamortized, thanks to Overmars and van Leeuwen, but you really don't want to do that if you don't have to.

[These notes](http://compgeom.cs.uiuc.edu/~jeffe/teaching/datastructures/notes/01-statictodynamic.pdf) cover the basics.

Cache-oblivious lookahead arrays are the mutant offspring of Bentley-Saxe and van Emde Boas trees on steroids.

> **Comments:**
> **username_4**: Those are beautifully written and illustrated notes, and I have used them as a reference many times. Thanks for making them available!  
> **username_4**: I see how shuttle trees (from the first half of the paper introducing cache oblivious lookahead arrays) are related to vEB trees, but what is the relationship between COLAs and vEB trees?  
> **username_0**: Thanks, this material seems a very interesting generalization of the idea. I have always thought that data structures are frozen algorithms, which you can run step by step, but I had never found a useful formalization of that intuition.  
> **username_6**: Did the first link work for anyone else?  
> **username_5**: Yes, I just tried it.  (Unfortunately, it goes to an Elsevier paywall; sorry!)  
> **username_7**: The link to the note breaks and probably should be replaced by http://jeffe.cs.illinois.edu/teaching/datastructures/notes/01-statictodynamic.pdf  

---

### Answer by username_4 on 2011-08-06. Score: 11

This is similar to a log-structured merge trees or [cache oblivious lookahead arrays](http://supertech.csail.mit.edu/papers/sbtree.pdf) (or COLAs).

The simplest COLA is an array of size $2^k-1$ with virtual "levels" of length $2^i$ for $0 \leq i < k$ laid out in order in the array. Each level is totally full or totally empty, and each level is sorted.

To insert an item, place it it level 0 (with $2^0$ length) if level 0 is empty. Otherwise, merge it with the item at level 0 and fill level 1 (with $2^1$ length) with the resulting list of length 2. If level 1 is already full, merge again; repeat.

Insert takes $O(\lg n)$ amortized / $O(n)$ worst-case time. Lookup takes $O(\lg^2 n)$ time. More advanced versions can reduce and partially deamortize these.


---

