8..15重複しない範囲 (例: 、16..19) を構造体へのポインターにマップするデータ構造が必要です。
その範囲内の任意の要素を検索して、そのポインターを取得できる必要があります。例えば：
structure[8..15] = 0x12345678;
structure[16..19] = 0xdeadbeef;
structure[7]; // => NULL
structure[12]; // => 0x12345678
structure[18]; // => 0xdeadbeef
現在、二分探索木の使用を検討しています。範囲が重複することはないため、対数時間で比較的簡単にインデックスを検索できます。
ただし、この場合により適したデータ構造があるかどうかは疑問です。効率的に挿入、削除、検索できる必要があります。これらの操作はすべて BST では O(log n) ですが、これを高速化する方法があるかどうか疑問に思っています。
O(log n) よりも高速なものが必要な場合は、Van Emde Boas treeを使用します。
二分探索木を使用するのと同じ方法で使用する必要があります。各範囲の開始をキーとして使用し、範囲の終了を値の一部として (ポインターと共に)、このキーにマップします。時間計算量は O(log log M) です。ここで、M はキーの範囲です (範囲の開始に整数値が可能な場合は INT_MAX)。
場合によっては、Van Emde Boas ツリーに大きなメモリ オーバーヘッドが発生します。それが受け入れられない場合は、Beni で説明されている単純なトライか、Y-fast トライを使用してください。
私はあなたがもっとうまくやれるとは思わない。
重複しない範囲は、一連の交互の開始点/終了点と同等です。したがって、ルックアップは「最大の要素 ≤ x を見つける」だけで、その後に O(1) チェックが開始または終了かどうかが続きます。つまり、順序付きマップです。
そのための通常の疑い - 二分木、B 木、さまざまな試み - はすべて本質的に O(log n) です。実際にはどちらが最適かは調整の問題であり、範囲について何か知っているかどうかに依存します。それらはまばらですか、それとも密ですか？それらは同じようなサイズですか、それとも大きく異なりますか? データはどのくらいの大きさですか (キャッシュ/RAM/ディスクに収まりますか)? 挿入/削除が多いですか、それともルックアップが支配的ですか? アクセスはランダムですか、それとも局所性が高いですか?
多くのスキームに適用できるトレードオフの 1 つは、範囲を分割して、同じポインターを複数の場所に複製することです。これにより、挿入/削除とメモリ使用量を犠牲にしてルックアップが高速化される場合があります。極端なアプリケーションは、ルックアップが O(1) で挿入が O(範囲のサイズ) である、ポイントでインデックス付けされた単純な配列です。これは、複数レベルの構造を必要とします: k 個の均一な部分範囲の配列で、1 つの範囲で完全にカバーされている場合は value を指し、そうでない場合は部分配列を指します。ねえ、私はトライについて説明しました！ルックアップは log(maxint)/log(k) であり、k が 2 のべき乗 (たとえば 256) の場合は非常に高速です。挿入とメモリは k*log(n) です。
ただし、メモリを浪費するとキャッシュのパフォーマンスが低下するため、そのような「最適化」は、ルックアップであっても実際には逆効果になる可能性があることに注意してください。