Applications of finger trees
1 Finger trees
Consider a data structure that maintains a sequence of monoid elements from . Say, the sequence is . It has four operations. All time are amortized and not worst case.
, is a monotonic predicate on , i.e. . It split the sequence at position , such that for all , and for all . This takes time.
, concatenate sequence represented by and the sequence represented by . If the length of the sequences are and , respectively, then this operation takes time.
, returns in time.
, apply to every entry in the sequence. So would represent . This operation takes time.
There is one operation that produce an empty sequence.
We have to first make a few assumptions: All monoid operations take time. All map we consider can be evaluated in time AND we can compute in time. Note this means we compute (a representation) of the function itself, and we can use this representation to compute in time.
Otherwise, all " time" should be replaced with " monoid operation, function evaluation, function composition and constant time operations.".
Such data structure exists. The first operation are supported by finger tree . It is not hard to add the last operation, the idea is to tag nodes with an function (in the beginning is just the identity), and it means "apply to everything below!". It propagate only when the lower level nodes need to be accessed, therefore the cost would be charged into the other operations. Many other binary search trees probably can implement these operations too. For example, if the dynamic optimality conjecture for splay tree is true, it be best to use splay tree for implementation. However, that's beside the point. The point is to have an abstract data structure over a monoid sequence. The abstraction deals away with all the mess hidden by the data structure.
2 Extend its power
Finger tree can be extended to query elements by giving indices of the element: take the Cartesian product of the monoid and , and we get a new monoid. So we can just assume our data structure has the following extensions:
, split the sequence to two sequence and at the th index in time.
, insert element to the th position.
, delete the element at th position.
Another interesting extension is allowing one to the sequence in time. This become much more complicated.
There are some common application of finger trees.
Stack, queue, dequeue with product operation, all amortized constant time. As a special case, it would solve the min stack problem.
Random access sequence, which is related to the rope data structure.
Ordered sequence(sorted list).
Interval trees, segment trees.
Most of the above has been described in , but we will talk about two specifics that usually not mentioned by others.
3.1 Merge sorted lists in optimal time bound
If and are two ordered sequences of length and , respectively. . Both ordered sequences are represented by finger trees. Compute the finger tree representation of takes time.
Split into pieces one by one by split along the th element of to the second part of the th produced piece for all , then concatenate all of them. The splitting takes time, where is the size of the th piece. By concavity, we have the time for split is , and concatenation time is similar.
3.2 Solve the Klee's measure problem
This section shows how the map operation is quite crucial because we can make range updates.
The motivation came from the following question. Can finger tree substitute for the popular competitive programming data structure segment tree, a special case of the real segment tree? This is not possible, and it's not because the large hidden constants. The abstract definition in this article goes cannot do the following common operation on an sequence of integers: increment the th number by . This operation make little sense if we allow insert and deletions, but many use of segment tree do not consider insert and deletes.
Fortunately, Klee's measure problem, the problem that caused the invention of segment tree can be solved with a finger tree. We show how to solve it in 1D. It's well known how to use it for solving the D version.
We produce another data structure, such that each operation takes amortized time. Where is the number of times we called insert.
We maintain a collection of intervals with data structure , there are 3 operations.
- , insert interval into the collection.
- . Delete a interval from the collection, we assume it's always a interval inserted before.
- . Find the measure of the union of all intervals in the collection.
It can be sharpened such that is the number of intervals inside the data structure. We just do a global rebuild if the number of interval doubled or reduced to half since the last global update. Also, actually only take constant time.
The finger tree stores a sequence of elementary intervals that partitions the space, and how many copies of that interval exists. Thus we can represent it as , where is the elementary interval with left and right boundary, and is the number of copies.
To insert a interval, consider it's left point . The data structure find a elementary interval contains , and split it into two elementary intervals. Similarly, we do the same with the right endpoint. This takes time, and we increase the number of elementary intervals by at most . is an automorphism defined as . For each insertion of interval , gets applied to all elementary interval in the range. For deletion, we apply instead.
The monoid product is simply , and this is exactly what should output.
3.3 The local ranking sequence
The ranking sequence of a sequence of distinct numbers is defined as , where is the th smallest element. Given a sequence of unique integers , we want to design a data structure to query , which returns the ranking sequence of .
This can be solved by storing sorted subsequences. We just have to return sorted sequence of during the query, and then it become simple to figure out the ranking sequence. This will make sure the running time for to be . There are a few other variants, but seems quite hard to adopt a finger tree for .