問題タブ [interval-tree]

長方形 (x、y、幅、高さ) またはポイント (x、y) のリストに変換できる部屋と通路のセットがあります。RoomどちらもインターフェースをPassage拡張しPointableます。getPoints() メソッドは、Room クラスに対して次のように実装されます。

問題:特定のが属する を
特定する必要があります。交差する部屋はありません。私はもともと a を使用して、それぞれを aに関連付けました。これにより、O(n) 時間ですばやく答えにアクセスできました。ただし、レベルの生成では複数回再計算する必要があります。この時点で、(生成とアクセスを考慮して) HashMap を使用する方が効率的ですか? それとも、2 次元間隔ツリーのセットなど、別の方法を使用する必要がありますか?PointablePointHashMap<Point,Pointable>PointPointableHashMap

【チャレンジ終了】

問題：

正の要素の配列。Deepu 配列の要素を減らしたい。彼は、X より大きい配列内のすべての要素を 1 だけ減らす関数 Hit(X) を呼び出します。

彼はこの配列を何度も呼び出します。Hit(X) を何度も呼び出した後、配列を出力します。

入力：

n----- 配列 10^5 の要素の数。

n 個の要素 ----- 1<=要素<=10^9。

x----- Hit(X) x 要素への呼び出しの数----- 1<=要素<=10^9。

出力：

出力 Hit(X) x 回の呼び出し後の配列。

制限時間・・・5秒。

私の解決策はTime Limit Exceededを与えました。

私のアプローチ：

1. 元の配列を保持
2. 配列要素と配列内のインデックスのペアのベクトルを作成します。ベクトル要素を [昇順] で並べ替えます。
3. C++ STL の LowerBound() を実行して、要素が等しいベクトル内の要素の位置を取得し、要素 x を指定します。
4. この要素から、ペアのインデックスから元の配列の最後まで、x より大きい要素を 1 ずつ減らします。
5. x ごとに手順 3 と 4 を繰り返します。
6. 元の配列を印刷します。

私のソリューションの複雑さは n^2 だと思います。

最適化されたソリューションを教えてください

ありがとう

マイコード

次のプロパティを使用して、閉じた間隔で効率的に動作するデータ構造を探しています。

• 間隔を動的に追加または削除する

• 各間隔の数値 (「深さ」) を設定し、いつでも変更できます。同じ深さは 2 つとありません

• 「深さ」でソートされた、特定の間隔と重なるすべての間隔を見つける

私が見つけた最も近い構造は間隔ツリーですが、見つかった間隔を深さに関して任意の順序でリストしています。報告されたすべての「ソートされていない」間隔を収集し、後でソートすることはできましたが、すべてのクエリの結果をソートすることを避けることができました。

誰かがそのようなデータ構造を知っているか、またはそのようなソートをサポートするために間隔ツリーを拡張する方法 (可能な場合) を提案していますか?

例：

1. [1,2] を空の構造に追加し、その深さを 1 に設定します
2. [10,100] を追加、深さ = 2
3. [5,55] を追加、深さ = 3
4. [5,50] レポート [10,100] および [5,55] のクエリ
5. [10,100] の深さを 3 に、[5,55] の深さを 2 に設定します。
6. [5,50] レポート [5,55] および [10,100] のクエリ

編集

深さの更新よりも、高速な追加/削除とクエリに興味があります。深さは、他の操作の高速化に役立つ場合、O(n) までかかる場合があります。

このトピックについて少しグーグルで調べたところ、http://www.geeksforgeeks.org/でこれを見つけました。

インターバル ツリーは主に幾何学的データ構造であり、ウィンドウ クエリによく使用されます。たとえば、長方形のビューポート内のコンピューター化された地図上のすべての道路を検索したり、3 次元シーン内のすべての可視要素を検索したりします。

今、私の質問は実際には2つの部分に分かれています:

• コンピュータ化された地図上のすべての道路を見つけるために、インターバル ツリーはどのように使用されますか?
• インターバルツリーの実用的なアプリケーションの他の例は何ですか?

PS: インターバル ツリーに関するより多くの読み物を参照した簡単な説明は大歓迎です。

C#でインターバルツリーを書いています。私がやりたいことは、既存の二分探索木を拡張して間隔を保存することであり、コア機能 (追加、取得、削除) を書き直す必要はありません。

BST 内には、Nodeクラスがあります。

インターバル ツリー内には、IntervalNode拡張するクラスがありますNode。

私が直面している問題はIntervalNode、 ではなくツリーに保存しようとしていることですNode。Addwithの既存の基本実装を使用できる方法はありますIntervalNodeか?

私ができるようになりたいのは、次のようなものだと思います。

サイズ n の配列が与えられ、1 から n までの各 k について、サイズ k の連続する部分配列の最大和を求めます。

^{この問題には、時間計算量 O(N 2} ) と O(1) 空間の明らかな解があります。ルアコード:

時間の複雑さが低いアルゴリズムはありますか? たとえば、O(N log N) + 追加メモリ。

関連トピック：

• カダネのアルゴリズム

セグメント化されたツリーの遅延伝播アルゴリズムには、私には不明な点があります。以下のコードによると、クエリ間隔が完全にオーバーラップすると、更新値が親ノードに追加され、子は遅延更新用にマークされます。しかし、添付の画像でわかるように、範囲 0,1 に対して +4 の更新が行われると、結果は両方のツリーでまったく異なります! (左の画像: 遅延伝播なし)。

問題は、0,1 からの合計を求めるクエリが +4 更新後に呼び出された場合はどうなるかということです。

循環間隔を処理する (できれば JavaScript) 間隔ツリー アルゴリズムを実装した/知っている人がいるかどうか疑問に思っています。循環とは、開始 > 終了の間隔を意味します。これには、間隔の大きさの上限も必要になることに注意してください。

これは、一般的な間隔ツリーの問題の単なるサブケースですか?

コメントで寄せられた質問への回答: これは、円形部分範囲の意味を示すイメージです (G. Bach とウィキペディアに感謝します)。

そして (上の画像とは関係ありません) 範囲の json 表現の例を次に示します: [{id: 'range1', start: 3, end: 34}, {id: 'range2circular', start: 30, end:6}]

望み

ありがとう！

インターバル ツリーの記事で増補ツリーを見て、SWI-Prolog 標準ライブラリのrbtrees.plを見ています。記事には次のように書かれています。

次に、追加の注釈がすべてのノードに追加され、このノードから下のすべての間隔の中で最大の上限値が記録されます。この属性を維持するには、ノードが追加または削除されるたびに、ノードのすべての祖先をボトムアップで更新する必要があります。

この注釈を追加する方法は簡単にわかります。interval を保存したいとします7-45。キーとして 7 を使用し、値にはすべての情報を含む構造体を使用するので、interval(7-45, MaxBelow). しかし、「ノードのすべての祖先を更新する」方法は明確ではありませんrb_insert/4。前のツリーと後のツリーの間で変更されたすべてのノードのリストを取得する方法がわかりません (とにかく、そのようなリストを生成するのはおそらく奇妙で非効率的です)。

でこの構造を構築するこのアプローチを進める方法はありrbtrees.plますか?

ちなみに、rb_emptyインスタンス化されていない変数を空のノードとして使用するのは興味深いことです。これには理由がありますか？

編集：前後のツリーを調べて、前後のブランチを統合して、変更された場所のパスを見つけることができると思います。それは私が求めているパフォーマンスの向上を台無しにするつもりですか?

問題は：

• 長さ n の文字列と m のクエリを指定します。

• 各クエリは、次の 2 つのケースのいずれかです。

  • i 番目の文字を逆に変更する
  • u 番目の文字から v 番目の文字までの部分文字列が正しいかっこ式であるかどうかを確認します。はいの場合は 1 を出力し、そうでない場合は 0 を出力します。

制限時間：0.2秒

これらの場合、正しいブラケット式が定義されます。

• 長さが 0 の文字列

• '(' と ')' のみを含む文字列

• A が正しいブラケット式の場合、(A) も正しいブラケット式です

• A と B が正しい括弧式の場合、AB も正しい括弧式です

私の主なアイデアは、CodeForces の問題380Cに似ています。 http://codeforces.com/blog/entry/10363

次に、指定された範囲内の最長のサブシーケンスが範囲の長さと等しいかどうかを確認して、答えを取得します。しかし、時間制限エラーが発生しました。

私は一日中インターネットでこれを探していましたが、答えがありませんでした。あなたが私を助けてくれれば、私は感謝します。:)

これが私のコードです: https://github.com/hoangvanthien/GH_CppFiles/blob/master/SPOJ/NKBRACKE.cpp