1

0 に初期化された配列 arr が与えられた場合、つまり arr[i]=0 ここで 0 < i < n

その上で2つの操作が実行されます

  1. krxを更新する

    更新は次のことを行います。

    for(i=k;i<=r;i++)
{
    arr[i]=x;
    x+=x;
}

  2. クエリ kr

    クエリは次の合計を計算します。

    for(i=k;i<=r;i++)
{
    sum+=arr[i];
}
print(sum);

私の解決策：
ブルートフォースを考えましたが、遅いです。セグメントツリーを考えたのですが、セグメントツリーでは一定量ずつ更新されるので失敗します。これを解決するための良いアルゴリズムは何でしょうか?

拘束する

配列のサイズは <=10^5 です

操作数(更新、クエリ) <=10^5

4

1 に答える 1

2

あなたが探しているのはLazy Propagation in Segment Treesです。セグメント ツリー配列と同じサイズの配列 lazy[] を作成します。update での再帰呼び出しを延期することで回避し、必要な場合にのみ更新を行うという考え方です。

以下のコードは、事前定義されたデータの更新と合計抽出を行います。メインをいじって、目的のパターンでユーザー データを受け入れ、x+=x などの微調整を追加できます。

https://ideone.com/kZsJ0E

遅延伝播は理解するのが難しいことが多いため、コードを開いて以下の説明を並べて読んで理解を深めることをお勧めします。

使い方：

  • 最初に、lazy[] 配列内のすべてのエントリは 0 に設定されます。これは、そのノードが表す範囲で実行する残りの作業がないことを意味します。

  • qs (クエリ開始) から qe (クエリ終了) までの配列インデックスでセグメント ツリーを更新するには:

    -> 現在のセグメント ツリー ノードに保留中の更新がある場合、そのノードに (lazy_value)*(それが表す間隔の長さ) を割り当て、その子の遅延値を new_value として割り当てます。

    -> 現在のノードの範囲が完全に更新クエリの範囲内にある場合。

    i) Update the Current node, by assigning it (lazy_value)*(length of interval it represents)

ii) Postpone updates to children by setting lazy values for children nodes as new_value

    -> 現在のノードの範囲が更新範囲と重複する場合は、上記の単純な更新と同じアプローチに従います。

    a. 左と右の子に対して繰り返します。

    b. 左右の呼び出しの結果を使用して現在のノードを更新します。

  • ここで、get_sum プロシージャを使用すると、保留中の更新がある場合は現在のノードも更新され、子への更新が延期されます。

全体として、遅延伝播の全体的な動作をここで説明するのは困難ですが、コードと説明が役立つことを願っています。

遅延伝播の詳細については、次を参照してください。

https://www.hackerearth.com/notes/segment-tree-and-lazy-propagation/

于 2016-01-06T15:15:23.243 に答える