大きな (> 百万要素) ツリーがあり、各要素には外部のものを参照する「オフセット」フィールドがあります。私は両方を行う必要があります:
2 が必要でない場合は、前のオフセットに対する相対的なオフセットを保存します。挿入後にすべてを更新する必要はありません。しかし、それは、1 つの要素の絶対値を計算するために、以前のすべてのオフセットを合計する必要があることを意味します。
この種のことを行う標準的な方法はありますか？たとえば、n 番目の要素ごとに絶対オフセットがあり、他の要素のオフセットは前の絶対オフセットに相対的であり、どちらの場合も少量のトラバーサルを行う必要があるという妥協案を考えていました。
一部の要素に絶対オフセットを格納させるという考えに基づいたアプローチがいくつかあります。
そのうちの 1 つ (階層化された vectorのバージョンだと思います) は、最初の連続する要素のオフセットの変更を保存し、次にtosqrt(N)の要素などを保存することです。次に、特定の要素のオフセットを見つけるために、前の要素の連続した合計をすべて合計する必要があります (これは最大でです。これにより、挿入と検索の時間が得られます。sqrt(N)2 * sqrt(N)sqrt(N) + 1(sqrt(N) ^ 2) = NO(sqrt(N))
このアプローチを次のレベルに進めて、以下の合計を保存することもできます。
このようにして、インターバル ツリーまたはセグメント ツリーに似たデータ構造が得られますが、まったく同じではありません。単純な配列を使用して、完全なバイナリ ツリーとして実装できます。O(log N)両方の操作が複雑になります。
この考え方を少し改良した結果、Binary Indexed Treesが生まれました。複雑さは同じですが、使用するスペースは約半分です。