問題タブ [segment-tree]

質問する

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

262 問題
Newest
Active
Bountied
318
Unanswered
0 投票する
1 に答える
267 参照

memory-management - SPOJ ポスターのセグメント ツリーでメモリ制限を超えましたか?

wall の水平断面と、座標 Xi から Yi まで適用されたペイントの N 層が与えられた場合、可視層の個別の数を出力します。

ここに問題のリンクがあります http://www.spoj.com/problems/POSTERS/

これが私の解決策ですhttp://ideone.com/gBJKnL

アプローチ: セグメント ツリーを介して子ノードの値を遅延更新することで問題を解決しようとしました。最新の値は、遅延更新で古い値を置き換えます。このようにして、最近のペイントのみが水平断面に適用されます。コードはカスタム テスト ケースでは問題なく動作しますが、多くのメモリを消費し、オンライン ジャッジによって中止されます。

0 投票する
1 に答える
320 参照

arrays - セグメント ツリー上の Josephus Flavius

セグメント ツリーを使用して、Joseph Flavius 問題を解決したいと考えています。単純なシミュレーション (つまり、並べられたリスト) はO(n^2). 私が達成したいのは、セグメントツリーから取得した特定の距離の配列にジャンプすることです。つまり、セグメントツリーは削除された要素の数に関する情報を保持し、ツリーから情報を取得すると、O(1) で削除する次の要素を見つけることができます。問題は、Joseph Flavius 問題で機能するようにセグメント ツリーに情報を保存する方法がわからないことです。

各ノードに保持される何らかの追加の値はありますか? しかし、次の要素に関するクエリを作成するにはどうすればよいでしょうか?

0 投票する
1 に答える
55 参照

c++ - セグメント ツリーのノード構造が明確でない

セグメント ツリーを構築しようとしていますが、ノード構造が明確ではありません。見つけたコードを誰か説明してください。

0 投票する
2 に答える
1956 参照

arrays - 頻度を計算するためのセグメント ツリー

セグメント ツリー構造を使用して、配列内の特定の値の頻度を計算する方法はありますか?

サイズ N の配列 A があり、配列のすべての要素 A[i] に値 0、1、または 2 が含まれているとします。次の操作を実行します。

  • 配列の任意の範囲 [a,b] のゼロの量を計算します
  • 配列の任意の範囲 [a,b] 内のすべての要素をインクリメント (mod 3) します

例: A = [0,1,0,2,0] の場合:

  • [2,4] の範囲には 0 が 1 つあるため、Query[2,4] は 1 を返す必要があります。
  • Incre[2,4] は、A を [0,2,1,0,0] に更新します。

これは、セグメント ツリーを使用して解決できる (この場合は、範囲の更新のために遅延伝播を使用する) 範囲合計クエリの問題によく似ていますが、セグ ツリー コードをこの問題に適応させることに成功しませんでした。通常の RSQ のようなツリー内の値では、値「3」を含む親ノード (たとえば) は何も意味しません。この情報では、この範囲に存在するゼロの数を抽出できないためです。

前もって感謝します！

--

編集：

セグメント ツリーは、配列に関連する区間をそのノードに格納するバイナリ ツリー構造です。葉ノードは実際の配列セルを格納し、各親ノードはその子の関数 f(node->left, node->right) を格納します。セグメント ツリーは、配列の範囲 [a,b] 内のすべての要素の合計を計算する範囲合計クエリを実行するためによく使用されます。この場合、親ノードによって計算される関数は、その子ノードの値の合計です。範囲合計クエリの問題を解決するためにセグツリーを使用したいのは、O(log n) で解決できるためです (範囲クエリで完全にカバーされるノードが見つかるまでツリーを下るだけです)。単純な O(n) アルゴリズム。

0 投票する
3 に答える
607 参照

algorithm - 範囲内の個別の要素の合計

配列 (0 ベースのインデックス) を考えてみましょう。0< i < n であるすべての可能な範囲 [i,n] の個別の要素の合計を見つける必要があります。

例：

O（n ^ 2）ソリューションは1つの可能なソリューションであり、永続的なセグメントツリーでもこれを実行できることを読みましたが、良いチュートリアルが見つかりません。

O(N^2)時間以内に解けますか?

誰かが永続的なセグメント ツリーを指摘している場合は、説明または適切なリンクを提供してください。

0 投票する
1 に答える
545 参照

algorithm - 配列を更新する

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

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

  1. krxを更新する

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

    /li>

  2. クエリ kr

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

    /li>

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

拘束する

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

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


12345678910