tree - すべての操作で配列の先頭に要素を追加し、指定された範囲の合計を計算するにはどうすればよいですか?

Question

N最初に整数の配列が与えられます( 1<=N<=105 )。この配列を指定すると、2 種類の操作を実行する必要があります。

(i) Operation 1 : Op1( l, r )

2 つの整数lとが与えられますr。( 1 <= l <= r <= current size of the array ). lとr(両方を含む)の間のインデックスを持つすべての要素の合計を返す必要があります。つまり、現在配列内にある要素が a1、a2、a3.... an の場合、次の を返す必要がありますsum : al + al+1 + al+2 ... + ar。

(ii) Operation 2 : Op2( x )

単一の整数 x が与えられます( |x| <= 109 )。この要素を配列の先頭に追加します。この操作の後、xは になりa1、 はold a1になりa2ます。配列のサイズは だけ増加し1ます。

最初に与えられた配列でセグメントツリーを作成し、範囲合計を計算できました....しかし、セグメントツリーに1つの要素を追加して、それに応じて変更するにはどうすればよいですか?

Answer 1

このオフラインアルゴリズムを試してください:-

最初に配列 a を読み取ります。

次に、すべてのクエリを読み込んで保存し、タイプ 2 のクエリの数も数えます。それを K とします。

ここで、長さ K+(a) の長さの新しい配列 b を作成します。

ここで、b のインデックス 1 から開始し、クエリを逆方向にたどって、タイプ 2 クエリごとにその要素を配列 b に追加します。

ここで、アレイ b にセグメント ツリーまたはバイナリ インデックス ツリーを構築します。

変数 c を使用して、これまでに発生したタイプ 2 クエリの数をカウントし、0 に初期化します。

次に、クエリのリストをトラバースし、タイプ 2 のクエリごとに c を 1 ずつ増やします。

配列 a の範囲 l...r を持つタイプ 1 のクエリの場合、配列 b の範囲は (l+kc)...(r+kc) に対応します。

したがって、上記で作成したセグメント ツリーまたはバイナリ インデックス ツリーを使用して、変換された範囲でこのクエリに答えます。お役に立てば幸いです。