Как компрессировать упорядоченный массив уникальных натуральных чисел огр. диапазона?
Вообще это run-length encoding. Находить пересечение и разность можно без распаковки, просматривая параллельно оба набора, а вот проверку произвольного числа можно будет сделать тоже только просмотром, не очень эффективно.
Для ускорения сравнения в случае с предположительно малым общим ядром можно из каждого набора сделать Bloom Filter (для которого можно балансировать точность/потребление памяти). Тогда придется проверять вхождение только для тех элементов, для которых проверка по фильтру вернет «in set».