Efficient immutable data structure for small multi-sets of integer ranges?
I would suggest looking at interval trees and segment trees.  A natural representation is that the data structure contains a union of non-overlapping ranges $[l,u]$ with a multiplicity $m$; the intended meaning is that each integer in the range $l,l+1,l+2,\dots,u$ occurs in the domain with multiplicity $m$ (i.e., appears $m$ times), and the invariant is that the multiplicity of all integers within a single range is the same.

We can't tell you whether a tree would be faster in your application; that's workload-dependent, so the only way to tell is to try it and benchmark it and see.

This can be made persistent using standard techniques (e.g., path copying), if that's useful (e.g., if you have many domains that are similar to each other).