Struktur data apa yang secara efisien menyimpan rentang bilangan bulat?

Saya perlu menyimpan koleksi pada bilangan bulat dalam kisaran 0 hingga 65535 sehingga saya dapat dengan cepat melakukan hal berikut:

• Masukkan bilangan bulat baru
• Masukkan berbagai bilangan bulat yang berdekatan
• Hapus bilangan bulat
• Hapus semua bilangan bulat di bawah bilangan bulat
• Uji apakah bilangan bulat ada

Data saya memiliki properti yang sering mengandung bilangan bulat dalam koleksi. Misalnya, koleksi mungkin pada satu titik waktu:

{ 121, 122, 123, 124, 3201, 3202, 5897, 8912, 8913, 8914, 18823, 18824, 40891 }

Pendekatan paling sederhana adalah dengan menggunakan pohon biner seimbang seperti C ++ std :: set, namun, dengan menggunakan itu, saya tidak memanfaatkan fakta bahwa saya sering memiliki angka. Mungkin akan lebih baik untuk menyimpan koleksi rentang? Tetapi itu berarti rentang harus dapat dipecah jika bilangan bulat di tengahnya dihapus, atau bergabung bersama jika ruang antara dua rentang diisi.

Apakah ada struktur data yang ada yang cocok untuk masalah ini?

Saya sarankan Anda menggunakan pohon pencarian biner, ditambah sehingga daun dapat berisi interval (serangkaian bilangan bulat berturut-turut). Pertahankan invarian yang intervalnya tidak tumpang tindih dan berurutan (mengikuti invarian tree pencarian). (Ini dapat dianggap sebagai kasus khusus dari pohon interval atau pohon segmen, untuk kasus khusus di mana intervalnya tidak tumpang tindih.)

$O(\lg n)$$n$$n\le 65535$$O(\lg n)$

Pertama-tama, pertanyaan Anda sangat buruk, jika tanpa alasan lain karena "cepat" tidak banyak berarti. Anda harus memberikan beberapa metrik arti "cepat".

Di luar itu, ketika mencoba membuat desain untuk suatu masalah, Anda harus terlebih dahulu memahami masalah dengan baik dan mengajukan banyak pertanyaan tambahan . Pertanyaan yang relevan dalam kasus ini tampaknya (tanpa urutan tertentu):

• Haruskah semua operasi ini sama cepatnya, atau ada yang lebih penting daripada yang lain?
• Apakah ada pertimbangan lain?
• Apakah ingatan itu memprihatinkan?
• Apakah kemampuan untuk melakukan penyisipan, pemindahan, dan pencarian dari banyak utas menjadi perhatian?
• Apakah beban kerja sebagian besar terfokus pada penyisipan? Menghapus? Mencari?

$[0, 65535]$

Untuk sedikit lebih banyak pekerjaan, Anda bisa menghemat ruang jika itu menjadi perhatian, dengan mengorbankan kecepatan dengan menyimpan data sebagai bit dalam 8192 bilangan bulat. Meskipun secara konseptual operasi bilangan bulat tunggal akan tetap menjadi waktu yang konstan dan operasi bilangan bulat berkisar akan menjadi waktu linier, mereka akan lebih lambat.

Jadi, jika ini benar-benar masalah Anda, saya akan mengatakan gunakan array dan beralih ke hal lain yang lebih penting dengan kode.

$[0, 65535]$ dan Anda berusaha menyederhanakan masalah yang Anda tanyakan) maka Anda perlu untuk mengajukan pertanyaan Anda lagi, kali ini memberi tahu kami masalah sebenarnya .

$\mathcal{U}=\{0,\ldots,u-1\}$$O(\log \log u)$

Tergantung pada struktur data Anda, mungkin ada banyak alternatif cerdas cara menyimpan data Anda.