Data structure optimized for merging maps on partitions
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.