Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?
Here is one space-efficient memory-hierarchy-aware in-memory data structure that might be a reasonable choice.  The data structure is a binary search tree with 16-byte nodes.
Each node is either an internal node or a leaf node:

An internal node points to two children.  It has a value $v$, a left child $\ell$, and a right child $r$.  All integers $\le v$ are in the left child; integers $&gt;v$ are in the right child.

A leaf node holds a run-length encoding of a bitmap.  Notice that an interval has a very short run-length encoding, so this is slightly more general than storing an interval in each leaf (it is a hybrid somewhere between a binary tree of intervals and a binary tree of bitmaps).


Each node of the tree is responsible for some interval of integer values $[s..t]$.  The root is responsible for $[0..\text{MAX}-1]$.  For an internal node containing the value $v$, its left child is responsible for $[s..v]$ and its right child is responsible for $[v+1..t]$.  A leaf that is responsible for $[s..t]$ has a run-length encoding of the bitmap for the integers in the interval $[s..t]$.
How do we pack each node into 16 bytes?

I'll assume the tree contains at most $2^{32}$ nodes in the tree.  Therefore, each node can be referred to by a 32-bit label.  We'll have an array $A$ of nodes, and the node with label $i$ will be stored at $A[i]$.  With this optimization, each child pointer can be stored in 32 bits (rather than 8 bytes for a 64-bit pointer).  Note that the restriction to $2^{32}$ nodes is not very restrictive; unless your machine has more than 64 GB of RAM, you couldn't fit anything larger in memory anyway.

I'll assume that $\text{MAX} \le 2^{64}$.

The first bit of the node will indicate whether it is an internal node or a leaf node, leaving 127 bits for the rest.

Internal nodes: We need 64 bits for the two child pointers.  That leaves us 63 bits for the value $v$.  We'll store the value $v$ as an offset within the interval for that node.  In other words, if the internal node is responsible for the interval $[s..t]$, then we'll store $v$ as the value $v-s$.  (We know $v \in [s..t]$, so it follows that $v-s$ is a non-negative integer.)  A 63-bit unsigned int is plenty for this offset.  (If we wanted to use an offset that is larger than will fit in a 63-bit unsigned int, then we just split the range artificially.  Since $\text{MAX} \le 2^{64}$, this will impose at most one or two extra splits at/near the root.)

Leaf nodes: We have 127 bits for the run-length encoding of the bitmap corresponding to the interval $[s..t]$.  We can use any convenient run-length encoding.  If the run-length encoding of the bitmap does not fit within 127 bits, we split the interval: we turn it into an internal node with two children.
If you know something about the typical distribution of lengths of runs (i.e., the lengths of intervals, the lengths of the gaps between intervals), you can choose a run-length encoding that is optimized for that distribution.  Otherwise, you can use any convenient generic run-length encoding scheme (e.g., recursive Rice-Golomb encoding); see also this Wikipedia page on compressed bitmaps.


Notice that we don't store $s$ or $t$ in each node, but that's OK.  The interval $[s..t]$ for a particular node is determined by the path that we took to reach that node.  As we traverse down from the root, we can keep track of the interval $[s..t]$ and update it each time we follow a child pointer.
If you wanted, you could combine with this with some sort of self-balancing binary tree scheme )or a self-optimizing binary tree, such as a splay tree), but it might not be necessary in practice, depending upon the access pattern in your application, and it definitely adds complexity.