Data structure optimized for merging maps on partitions My question is a request for literature or pointers that address the following abstracted problem. If I have a finite set (ex. {1..10}) over which I'd like to maintain several "partition maps":


m1 = {1..5}=1, {6..10}=2
m2 = {1..3,8..10}=3, {4..7}=4.


Afterwards I'd like to merge (generalize the operation, but use addition for demonstration) these maps:

m1 + m2 = m3 = {1..3}=4,{4,5,8..10}=5,{6,7}=6.

If n is the size of universal set, and k &lt;&lt; n the size of the range of the maps. How does one get performance (and space) closer to O(k) as opposed to O(n) (store an array)?

Edit (2017-11-14): I'm mainly interested in merge performance, lookup can be slow. To sharpen the question, there are a couple of approaches to this problem that don't quiet address this trade off:


Okasaki's Fast Mergeable Integer Maps
Erwig's Diets for Fast Set
Bonichon's A Mergeable Interval Map. This probably gives the closest of what I'm looking for, but unfortunately the exposition is a bit confusing and I'm not certain that there is the same tradeoff of merging above lookup.


Edit (2017-11-15): The application where I'm using this performs millions of merges. In the most common instance I have 4 of these maps and compute a new map. The keys are different states and the values are actually probabilities. The probabilities are discretized which is why lots of different states have the same values. It is a form of "compressed" computations. I can use an array to store these values, but this compressed form provides 100x performance currently, but I'm looking for a technique to improve upon that (I need to do billion of merges). As @D.W. described below, batched techniques would also be of interest.
I can't say that I have a fully satisfactory answer to my question. But I spent a bit of time implementing and writing about a data-structure to solve my needs here. I call the data structure a partition map. It is really just an association lists of list of integer intervals and values. The former have nicer properties, resting on top of fairly straight-forward interval comparison logic.