What data structure would efficiently store integer ranges?
I suggest you use a binary search tree, augmented so that leaves can contain an interval (a run of consecutive integers).  Maintain the invariant that the intervals do not overlap and are in order (following the search tree invariant).  (This can be considered a special case of an interval tree or a segment tree, for the special case where the intervals do not overlap.)

This data structure you can support all of your operations in $O(\lg n)$ time, where $n$ is the number of intervals.  Since we're guaranteed $n\le 65535$, I would expect this to be quite efficient.  (In particular, yes, you can split an interval into two pieces or merge two adjacent intervals into a single interval in $O(\lg n)$ time.)