問題タブ [segment-tree]

整数配列（サイズ10 ^ 5）では、操作は次のようになります。

1. インデックスLからRまでのすべての要素に対して特定の数値Xでビット単位のxor演算を実行します
2. インデックスLからRまでの数値の合計を求めます。

セグメントツリーとレイジープロパゲーションでそれを行うにはどうすればよいですか？

このような関数でセグメント ツリーを更新します。プロファイリングによると、ボトルネックは次のとおりです。

また、メモリ操作は高速ですが、再帰オーバーヘッドが原因であるかどうか疑問に思っていますが、その深さは通常 20 を超えていません。

プリミティブ プロファイラーから得られるものは次のとおりです。

• 4.39434ms - データに対する単一バイナリ検索の平均時間
• 2642.94ms - 1 回の更新からの時間
• 19.9097ms - 単一の RMQ クエリの時間。

だから..単一の更新に費やされる時間は劇的です:)。

回答: 非表示の std::find オーバー マップが 1 つ見つかりました。

この構造がどのように機能し、どのように更新するかについては良い考えがありますが、Lazy Propagationで機能する場合は、何をすべきかわかりません。多くの問題で、これが競技会に合格する必要があるため、方法を知りたいです。それを機能させるために。

私はspojでこの問題を試しています：http ：//www.spoj.com/problems/CDC12_H/

誰かが怠惰な伝播をこの状況にどのように適応させることができるかを私に説明できるなら、私はそれを取り、アイデアに取り組みます、私にとってのアイデアは自分でこれを機能させることですが、少し助け。

誰かが私の問題の解決策を持って来ることを願っています。

現在、セグメントツリーの問題を解決しています。問題を解決するには、怠惰な伝播の概念が必要だと思います。私はこの概念に非常に慣れていないので、コードに問題があります。

一言で言えば、問題は次のとおりです。

最初は、すべての配列要素は0であり、0からN-1のインデックスが付けられています。

コマンド1.0xyv-xとyの間の各配列インデックスの値をvで更新します

コマンド2.1xy-配列インデックスxとyの間のすべての数値の合計を出力します。

入力は整数T（≤5）で始まり、テストケースの数を示します。

各ケースには、2つの整数n（1≤n≤105）とq（1≤q≤50000）が含まれています。次の各q行には、次のいずれかの形式のタスクが含まれています。

0 xyv（0≤x≤y<n、1≤v≤1000）

1 xy（0≤x≤y<n）それぞれの場合について、最初にケース番号を印刷します。次に、クエリ「1 x y」ごとに、xとyの間のすべての配列要素の合計を出力します。これが私の試みです：

範囲最小クエリ問題を解決するために作成されたセグメント ツリーにノードがいくつあるかを知りたいです。

また、ビルド操作にかかる時間とその理由は?

質問へのリンクはUVA-1394: And There Was Oneです。
単純なアルゴリズムは、配列全体をスキャンし、最後に停止する各反復で k 番目の要素をマークすることです。これには O(n^2) 時間がかかります。
私は代替アルゴリズムを検索し、O(N lgN) 時間の解決策として遅延伝播を使用してツリーをセグメント化することを指摘した中国のブログに出くわしました。 セグメント ツリーを調べた後、O(N lgN) 時間のアルゴリズムを作成しようとしましたが、役に立ちませんでした。

---

私の質問は次のとおり
です。 1. セグメント ツリーを使用して、希望の実行時間を取得できますか?
2. はいの場合、それらの使用方法を教えてください。
3. セグメント ツリーと「zkw」セグメント ツリーは同じですか? - 彼はブログで zkw セグメント ツリーについて言及しています。
更新:上記の問題は Josephus 問題の例です。

シナリオはありませんが、ここで問題が発生します。これは私を夢中にさせているだけです。nxnブール行列があります。最初はすべての要素が0、n <= 10 ^ 6であり、入力として指定されます。次に、最大10^5のクエリがあります。各クエリは、列cのすべての要素を0または1に設定するか、行rのすべての要素を0または1に設定することができます。別のタイプのクエリで、列cまたは行rに1の総数を出力することもできます。

私はこれをどのように解決するのか分かりません、そしてどんな助けもいただければ幸いです。明らかに、クエリごとのO（n）ソリューションは実行可能ではありません。

以下のリンクで、範囲を0に設定する関数をレイジー伝播の実装に追加したいと思います。現在、範囲をインクリメントするupdate_tree関数がありますが、それを変更して変更する方法がわかりません。 O（log（N））時間で範囲を遅延ゼロに設定します。

http://se7so.blogspot.com.au/2012/12/segment-trees-and-lazy-propagation.html

各ノードで「レイジークリア」フラグを使用することを考えていますが、最初にクリアしてからレイジー追加またはレイジー追加してからクリアすることをどのように知ることができますか（これはちょうどクリアになります）？

Python でセグメント ツリー クラスを実装しようとしています。セグメント ツリーを使用すると、対数時間の範囲でクエリを実行できます (セグメント ツリーの詳細については、 を参照してください)。私の実装では、範囲内の要素の合計に答えるために必要な情報を保持しています(i, j)。以下に私のコードがあります。私はPythonが初めてなので、各行の最後にセミコロンを使用しています(C++から継承)。

build 関数は、入力配列からセグメント ツリーを構築することになっていますa。プログラムを実行すると、次の出力が得られます。

シーケンスのすべての値が関数の終了24後にある理由がわかりません。build関数の実行中はデバッグ情報に他の多くの値が表示されますが、build関数が終了すると、すべての値が魔法のように に変わります24。なぜこうなった？前もって感謝します。

配列内の特定の間隔から最小値を抽出するためのセグメント ツリーを実装しようとしています。 [参照- http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

以下は同じコードです。

ツリーを構築している場合int(つまり、セグメント ツリーのノードを格納するために整数配列を使用している場合)、すべて正常に動作します。しかし、タイプを に変更するとすぐにfloat、何か問題が発生し、セグメント ツリーを表す配列のインデックス 0 ～ 7 とインデックス 11nanに値が表示されます。intツリーの場合、この種のことは何も起こりません。この関数printSegmentTreeArray()は、ツリーを表す配列の各位置に格納されている値を出力するためのものです。

ノート：-

int1. コード内で、ツリーのデータ型を からに正しく変更するために必要な変更は、置き換えられるの前のfloatコメント ブロックによって示されます。/* $$$ float $$$ */int

2.クエリされた間隔からMinを抽出する関数を作成しましたが、constructST()関数の動作がおかしいため削除しました。

3.両方のケースで、次の入力を使用してコードをテストしました。

誰かがこの理由を指摘できますか？