値が異なる 4 つの数値のリストがあるとします。その時点までのすべての数の合計を説明する 2 番目のリストがあります (list1=[1,3,2,5]、list2=[1,4,6,11] の場合)。このように、数十万の数のリストの場合、すべての数を追加する必要はありません。情報は既に保存されています。
list1 のインデックス 0 に新しい数値 (たとえば数値 2) を挿入すると、list2 の後続の値をすべて更新する必要があります。非常に大きなリストの場合、これには非常に時間がかかります (2 番目のリストの目的も無効になります)。
しかし、リスト (4) の前半の合計を記録すると、その合計から相対的に list2 を続行できます (list2=[1,4,2,7])。ここで、index=0 に数値 2 を挿入すると、最初の 2 つの値と記録された途中の値を更新するだけで済みます。100,000 個の数値のリストの場合、これにより、50,000 個の値のみを更新する必要があることが保証されます。
また、リストの 3 分の 1 ごと、または 10,000 個の数字ごとに値を記録することもできます。または、途中で記録することもできます (バイナリ ソートのようなものです。影響しているサブリストを更新/確認するだけで済みます)。
質問: このリストを管理する最も効率的な方法を特定するにはどうすればよいですか? 半分？三分の一？3 つのレベルで、それぞれ前のレベルを半分にしますか?
[これは実用的な問題であり、理論的な問題ではありません。List2 は、テキスト/グラフィックをレイアウトおよびレンダリングするためのオフセットを提供します。私が扱っているコンテキストでは、ツリーは実用的ではありません。単一のリストを処理する必要があります。特定の合計/オフセットにすばやくアクセスする必要があります。また、それを明確に提示するのに苦労しています。お気軽に質問を明確にするか、明確化を求めてください。]