数値{x0、x1、...、xn}ならセットを含むDSを実装したいと思います。以下に述べるニーズを満たすために使用できるデータ構造はどれですか？
初期化（n）は - 番号X0 = X1 = ... = XN = 0 O（N）最悪のケースを設定します。
Get（i） - xiの値を返します。 O（ログn）最悪の場合。
加算（d、i、j） - すべての数にxi、...、xjの値を加算します（i < = jと仮定）。 O（ログn）最悪の場合。
これらのDSを前述の時間の複雑さでどのように実装することができますか？ありがとうございました。
Iは、例えば、深さdの完全二分木、2^D> = N> = 2 ^（D-1）ツリーを構築することにより、そう5..8番号
g
e f
a b c d
1 2 3 4 5 6 7 8
ここで、すべてのリーフとすべての内部ノードに番号を関連付けます。
値を抽出するには、パス上のすべての数値をleaf-O（log n）時間に加算します。
数値の範囲に値を追加するには、上位から作業し、子孫がすべてその範囲内にあり、その親にその範囲内にいくつかの数値とその範囲にない数値があるノードにその値を追加します。例えば。 b、c、および7に3..7を加える。このような数のO（log n）以下でなければならない。なぜなら、各レベルで2つ以上のノードを更新する必要がないからである。
[OK]を繰り返し、範囲が重複するような追加をしたいとします。例題（1ベースの索引付け）には、次の「追加プログラム」があります： '[1..1] +1、[1..2] +2、[2..3] +3、[3..4 ] +4、[4..5] +5、[5..6] +6、[6..7] +7、[7..8] + 8 '（ここで '[i..j] + xは 'add（x、i、j）'を意味する）。あなたのalgoはどれくらい追加されますか？あなたが1..8を選んだだけで不公平だと感じたら、あなたのアルゴが優位性を示すことが明らかになるまで、自由に展開してください。 （それは、あなたの説明から得られないオーバーラップ範囲の後続の追加です。私は 'get（i）'をどのように実装するかも理解していません） –
アイデアは私たちがj - i =定数、O（log n）（O（log n）のk回）で追加するのは簡単ですが、主な考え方は、jiがO（n）でn/2と仮定すると問題に対処する方法です解決策は、O（log n）に到達するのに十分な高さを修正することです。大丈夫です。 – Obaf
それほど多くは真実ではない、と私は思わない。範囲に適用される値を表すデータ型を簡単に作成し、メモリ内の実際の数値ではなく、これらの値の範囲のリストとして値を表すことができます。そこから 'O（1）'に 'Add（d、i、j）'を実装するのは簡単です。しかし、このアプローチでは 'get（i）'を素早く行うことはできません。この問題は、O（log（n））の取得と追加の両方を行っているようです。 – Mshnik
"O（1）でAdd（d、i、j）を実装するのは簡単です。"次に、最初のものと重複する別の範囲に追加したい場合は、さらに何回ですか？ –