問題タブ [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 投票する
2 に答える
7726 参照

c++ - C++ のセグメント ツリーの STL

セグメント ツリーの STL はありますか?

競技プログラミングでは、セグメント ツリーのコーディングに多くの時間がかかります。そのためのSTLがあれば、多くの時間を節約できるのではないかと思います。

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

algorithm - 最も近い同数

a1..an数値といくつかのクエリがあるとします[l, k] (1 < l, k < n)。[l, k]問題は、2 つの等しい数の間の間隔の最小距離を見つけることです。

例: (間隔 l,k は |...| として示されます)

回答 2 (101)

回答 1 (22)

回答 2 (303) または (323)

セグメント ツリーも考えましたが、クエリが複数のノード間で共有されている場合、各ツリー ノードの結果を結合するのは困難です。それらに参加する方法をいくつか試しましたが、見栄えが悪いです。誰かが私にヒントを与えることができますか？

明確化

回答ありがとうございます。問題は、クエリが多いため、o(n) が良くないことです。誤ってセグメント ツリーについて言及したわけではありません。[l, r]検索[l, r]SUMまたは複雑[l, r]MINな配列でクエリを実行します。log(n)ここで o(logn) に収まるように前処理を行うことはできますか?

0 投票する
4 に答える
1626 参照

arrays - 範囲内の配列要素に特定の値を追加するための高速アルゴリズム?

範囲更新の質問で、範囲内の配列要素に値を追加したいと考えています。配列 (または何らかのデータ構造) がソートされていると想定できます。

単純なアルゴリズムでは、開始要素から終了要素までループし、各要素に値 v を追加します。

ただし、範囲が最初の要素から最後の要素までの場合、最悪の場合は O(n) 時間かかります。これを行うより速い方法はありますか？セグメントツリーを使用する必要がありますか?

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

time-complexity - セグメント ツリー - クエリの複雑さ

セグメント ツリーの複雑さを理解するのに問題があります。1 つのノードのみを変更する必要がある update 関数がある場合、その複雑さは log(n) になることは明らかです。しかし、（a、b）がチェックする必要がある間隔であるクエリ（a、b）の複雑さがlog（n）である理由がわかりません。これを理解するための直感的/正式な証拠を誰かに提供してもらえますか?

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

c - 2 つ以上のタイプのクエリに遅延伝播を使用する

4 つのタイプの多くのクエリに関する質問があります。

  1. 範囲に追加します。

  2. 範囲を初期化します。

  3. 範囲をスカラーで乗算します。

  4. ある範囲で現在の合計を見つけます。

膨大な数のクエリがあるため、遅延伝播でセグメント ツリーを使用する必要がありますが、2 種類以上のクエリで遅延伝播を使用する方法に行き詰まっています。後で更新が行われるときに、どのタイプの更新 (つまり、加算、乗算、初期化) が行われるかをどのように識別できますか?


12345678910