問題タブ [segment-tree]

Javaでの（バイナリ）セグメントツリーの適切な実装を知っていますか？

これを解決する方法がわかりません: http://acm.sgu.ru/problem.php?contest=0&problem=311

これで私を助けてください

セグメントツリーを使用して解決できることは知っていますが、方法がわかりません

以下は、セグメント ツリーの遅延伝播を使用したhttp://www.spoj.pl/problems/LITE/の実装です。ツリーを分割するのは初めてで、なぜ TLE になるのか理解できません。誰かがそれを見て、私のエラーを修正するのを手伝ってくれませんか?

Ruby での範囲ツリーまたはセグメント ツリーの実装を探しています。利用可能なサンプルまたは宝石が見つかりませんでした。

誰もサンプルコードを持っていますか?

ありがとう、

さて、私はこのCodechef でのコインのフリッピングの問題を解決しようとしていました。セグメントツリーで解決しています。しかし、制限時間を超えています。検索したところ、遅延伝播を使用する必要があることがわかりました。しかし、私には理解できません。私の更新機能は再帰的に（上から下へ）動作します。ヒントを与えるか、例を挙げて説明してください。また、コードを変更する必要がある場所も指摘してください。

コイン投げでは、更新時にノード値が 1 の場合は 0 に、0 の場合は 1 に変更します。

start と end は、元の配列の制限です。tree はセグメント ツリー配列です。

インターネット全体のセグメントツリーでの遅延伝播に関する優れた記事は1つしかないようです。それは、 http ：//www.spoj.pl/forum/viewtopic.php？f = 27＆t=8296です。

クエリノードのみを更新し、その子をマークするという概念を理解しました。しかし、私の質問は、最初に子ノードを照会し、後で親ノードを照会するとどうなるかということです。

このツリー内（ヒープの配列内の場所とともに）

最初のクエリ、[0 4]を更新すると、そのデータが変更され、その子にフラグが付けられます。2番目のクエリは、セグメント[09]の読み取り状態です。

ここで私は問題に直面します。私のセグメントツリーの実装では、各ノードの値はその左と右の子の合計になります。したがって、ノードの値を更新するときは、すべての親を更新する必要があります。論理的な問題を修正するために、ノードのすべての親を更新しています（ツリーのルートに到達するまで）。しかし、これはパフォーマンスを低下させており、高速バッチ更新にセグメントツリーを使用するという私の目的全体が失われています。

セグメントツリーの使用でどこが間違っているのか、誰か説明してもらえますか？

こんにちは、セグメント ツリーの問題を解決していましたが、セグメント ツリーのクエリ関数を少し変更することはできません。

実際に私が欲しいのは、クエリ関数がインデックス Qa と Qb の間の (int)(TotalArrayLength/3) 番目の最大要素を返すことです。

私が書いたクエリ関数は、index[1-based] a_begin と a_end の間の最大要素を返します。

しかし、インデックス[1ベース] a_beginとa_endの間の(int)(TotalArrayLength/3)番目の最大要素を返したいです。

クエリを作成するには、クエリ関数を query(1,0,N-1,QA,QB) と呼びます。

また、上記のクエリ関数を記述するために、次の擬似コードを実装しました。

では、index[1-based] a_begin と a_end の間の (int)(TotalArrayLength/3)th Maximum 要素を見つけるにはどうすればよいでしょうか。

基本的に、私が解決している問題は次のとおりです。

最初は、配列には 0 個以上の要素が含まれています。ランダムに一部のデータが配列の最後に挿入され、TotalArraySize/3 th Max Elements in Array build を返すクエリがいつでも実行されます。

また、目的に適したデータ構造を選択しましたか。

どうもありがとう。

データの配列からセグメント ツリーを実装しています。また、データの範囲を更新しながら、ツリーの最大/最小を維持したいと考えています。これは、このチュートリアルhttp://p--np.blogspot.com/2011/07/segment-tree.htmlに続く私の最初のアプローチです。残念ながら、まったく機能しません。ロジックは理にかなっていますが、bandについて少し混乱しています。これは配列eの範囲ですか? dataそれともツリーの実際の範囲ですか？私が理解していることから、は 範囲の を保持する必要がありますが、 範囲max_segment_tree[1]のを保持する必要があります。max[1, MAX_RANGE]min_segment_tree[1]min[1, MAX_RANGE]

EDIT テストケースの追加:

セグメント ツリーを使用して、SPOJ 問題GSS1 (これらのクエリに答えられますか?)を解決しようとしています。「init」メソッドを使用してツリーを初期化し、「query」メソッドを使用して範囲 [i,j] の最大値を取得しています。

リミット |A[i]| <= 15707 および 1<=N (要素数)<=50000。

ほとんどの場合 (負の数、奇数/偶数 N) のコードをデバッグしましたが、アルゴリズムの何が問題なのかわかりません。

誰かが私を正しい方向に向けることができれば、私は感謝します.

ありがとう

配列 A 内の次のクエリにすばやく応答できるように、セグメント ツリーを実装しています。

• クエリ i, j:範囲 (i,j) 内のすべての要素の合計
• update i, j, k: range(i,j) 内のすべての要素に k を追加します

これが私の実装です：

クエリ関数は非常に高速で、その複雑さは O(lg N) (N は ji) です。更新関数も平均的なケースでは高速ですが、ji が大きい場合、更新の複雑さは O(N lg N) であり、まったく高速ではありません。

この件について少し調べてみたところ、遅延伝播を使用してセグメント ツリーを実装すると、クエリと更新の両方の複雑さが O(lg N) になり、O(N lg N) よりも漸近的に高速になることがわかりました。

また、ポインターを使用するセグメント ツリーの実装が非常に優れている別の質問へのリンクも見つけました。. だから、ここに私の質問があります: ポインターを使用せずに、配列インデックスを使用し、segment_treeデータ構造を使用せずに、遅延伝播を実装するより簡単な方法はありますか?