問題タブ [segment-tree]

セグメント ツリー データ構造を使用して遅延伝播コードを作成しています。遅延伝播を行うために、セグメント ツリーのノードに整数のリストを格納し、遅延伝播を実行しながら、ノードの整数のリストを左右の子に追加したいと考えました。セグメント ツリーの更新メソッドの複雑さを Log(n) 時間に維持するために、ノードで遅延更新を O(1) 時間で実行したいと考えました。したがって、整数のリストを格納するには、Java で Vector または LinkedList を使用できます。Java のベクトルには addAll というメソッドがあり、LinkedList にも同じメソッドがあります。あるリストのすべての要素を別のリストに追加するだけで、2つのうちどちらがより最適化されるかを誰か教えてください。ありがとう

並べ替えられていない大きな配列が与えられた場合、特定の範囲内で特定の数値が出現する回数を調べる必要があります。（問い合わせが多いかもしれません）

たとえば、 arr[]={ 6,7,8,3,4,1,2,4,6,7,8,9}とleft_range=3andright_range=7とnumber=4の場合、出力は 2 になります (0 インデックス配列を考慮)。

arr[i] の範囲は 1 ～ 100000 です。配列には最大 100000 個の数値を含めることができます。

ここで使用するデータ構造またはアルゴリズムについて教えてもらえますか?

PS: 配列の前処理は許可されています。

セグメント ツリーについて読み終え​​たところです。時間の複雑さ O(log n) による挿入の証明は非常に説得力がありますが、同じ複雑さで削除を実行する方法を理解できませんでした。また、セグメントツリーが提案されている論文を探してみましたが、見つけることができませんでした.誰かが持っている場合は、リンクを投稿してください. 「JL Bentley、クレーの長方形問題のアルゴリズム。テクニカル レポート」

要約された問題: n 要素の配列が与えられました。最初はすべて 0 です。

2 種類のクエリを受け取ります: 0 index1 index2。この場合、範囲 index1 index2(included) 内のすべての要素を 1 ずつ増やす必要があります。

2 番目のタイプ: 1 index1 index2。この場合、index1 と index2 (含まれる) の間の要素が 3 で割り切れる数を表す数値を出力する必要があります。

もちろん、n は非常に大きい (10^6) ため、セグメント ツリーを使用して間隔を格納し、遅延伝播を使用してログ n のツリーを更新することも良い方法です。

しかし、実際には、ここで遅延伝播を適用する方法が本当にわかりません。コインを弾くように2つだけではなく、すべての数字（3k、3k + 1、3k + 2の可能性があります）に対して3つの可能な状態を考慮する必要があるためです。問題。

クエリの間隔に含まれる間隔にフラグを立てた場合、元の配列とその値を見て更新する必要がありますが、この間隔の息子を更新する必要がある場合は、同じことをしなければなりません繰り返しますが、これは時間の無駄です....

もっと良いアイデアはありますか？ネットで検索しましたが、何も見つかりませんでした...

編集:私はあなたの提案に従い、これ(C++)をコーディングし、いくつかの基本ケースで機能しますが、提出すると10/100ポイントしか得られません。何が問題なのですか? (少し長くてコメントが少ないことは承知していますが、遅延伝播を使用した単純なセグメント ツリーです。何かわからないことがあれば教えてください!

注: st[p].zero には、インデックス p に格納された間隔で 0 mod 3 の要素、st[p].one 要素 1 mod 3、および st[p].two 要素 2 mod 3 が含まれます。更新すると、これらの要素 (0->1、1->2、2->0) の位置が 1 つシフトし、lazy を使用します。更新時に、ペア < int 、ペア < int、int > > を返します。これは、3 つの数値を格納する単純な方法です。このようにして、数値 0,1,2 mod 3 の差を返すことができます。

セグメント ツリーとクワッド ツリーに関連する問題を解決しています。セグメント ツリーでは、1D 配列を2 (2^1)セグメントに分割し、ベース ケースが到着するまでこれを再帰的に行うことに気付きました。同様に、クワッド ツリーでは、2D グリッドを各ステップで4 (2^2)のセグメントに分割します。これらの分割統治メカニズムはすべて、対数時間の複雑さを達成するためのものです。悪意はありません！

しかし、セグメント ツリーの 2 つの部分ではなく、配列を4 (4^1)以上の部分に分割しないのはなぜですか? グリッドを 4 つではなく16 (4^2)の部分に分割しないのはなぜですか? O(log(N))これらを行うことで、パフォーマンスを達成できますがlog、log(N)(base 4) の方がlog(N)(base 2) よりも優れているため、パフォーマンスが向上します。

この場合、実装が少し難しいことはわかっています。メモリのオーバーヘッドの問題はありますか? それとも何か？

どこか間違っている場合は修正してください。ありがとう！

N 個の数字 (すべて正で、4 桁以下) を持つ配列Aが与えられた場合、 2種類のクエリがサポートされます。合計 M 個のクエリがあります。

1. インデックスL,R (両方を含む) で指定された範囲をKで更新します。
2. L,R (両方を含む)で指定された範囲内の最大の要素を返します。

数値をK回更新するということは、数値をK回回転させることを意味します。

たとえば、1234 は 2341 に回転します。

905 は 059 に回転し、059 は 590 に回転します。

注：059と59は別の番号です。59 は 95 に回転します。

指定された配列要素に先行ゼロがありません。

制約:

0 <= AI < 10000

1 <= N <= 800000

1 <= M <= 200000

0 <= K <= 60

ツリーノードが含まれる範囲の回転数を格納するセグメントツリーを考えました。これを遅延伝播で実装しましたが、遅延伝播でもクエリの実装に最悪の場合 O(N) 時間がかかり、TIME LIMIT EXCEEDED につながります。

誰でもより速いアプローチを提案できますか?

配列または構造体の一部のプロパティが不足していますか?