問題タブ [segment-tree]

C++ でセグメント ツリーをコーディングしたくて、再帰によるコード クエリ操作を書きましたが、遅くて TLE が発生します。したがって、誰かが反復を通じて次のコードを提案および説明できますか。これは大きな助けになります。

次のコードは、範囲にわたって gcd を計算します

ここ 、

Tセグメント ツリー

ss -セグメント開始

seセグメントの終わり

index - セグメント ツリーの現在のノード

L -クエリ境界の下限

R上限

配列がありarr[0 . . . n-1]ます。私たちはできるはずです

1. 0 <= L <= R <= n-1 であるインデックス L から R までの要素の合計を求めます。
2. arr[i] = x0 <= i <= n-1の配列の指定された要素の値を変更します。

これは、セグメント ツリーを使用して効率的に解決できます。

しかし、これとは逆に解決する方法、すなわち

1. L<= i <= R を除く、インデックス 0 から n-1 までのすべての要素 (arr[i]) の合計を求めます。ここで、L と R は指定されています。
2. array arr[i] = xwhere 0 <= i <= n-1の指定された要素の値を変更します。

上記の質問をセグメント ツリーのように効率的に解決するにはどうすればよいですか?

私はこの問題を解決しようとしています。

この問題のチュートリアルを見つけましたが、O(log n) (x は変更される可能性があります) で x より小さい数の量を見つけるセグメント ツリーを構築する方法がわかりません。チュートリアルでは省略されています。

誰も私にそれを行う方法を説明できますか?

これは質問リンクです - QSET - Codechef

これはエディトリアル リンクです - QSET - エディトリアル

基本的に、質問は、ある範囲[L, R]内の部分文字列の数を照会します。この問題を解決するために、セグメント ツリーを実装しました。私は社説を注意深くフォローしました。

structセグメント ツリーのノードを表すを作成しました。

このプログラムを高速化する方法を誰かに説明してもらえますか? ここでは、より高速な I/O が鍵になると思います。そうですか？

大規模なテスト ケース、つまりサブタスク 3 と 4 で TLE を取得しています (問題のページを確認してください)。サブタスク 1 と 2 については、受け入れられます。

[www.codechef.com/viewsolution/5909107] は承認されたソリューションです。scanfの代わりに が使用されることを除いて、コード構造はほとんど同じですcin。でも、私は をオフにしたsync_with_stdioので、それは差別化要因にはなりませんよね?

私はセグメント ツリーを学習しています(範囲最小クエリの例で) が、セグメント ツリーをクエリするためのアルゴリズムの一部の背後にある理由を理解するのに問題があります。

セグメントツリーの構築の部分を理解するのに問題はありませんが、この関数の理由を理解できません:

このノードのセグメントが指定された範囲の一部である場合、セグメントの最小値を返します。

私は現在fseek()プログラムで使用しています。また、ファイル内に出力される各行のバイトを追跡するバイト配列も維持しています。特定の位置へのアクセスが高速になるように、セグメント ツリーも使用しています。また、他のものを使用することは許可されていません...（構造体など）そうする方法はありますか？

セグメント ツリーを使用して、A のサブ配列の合計を見つけることができることを理解しています。また、こちらのチュートリアルに従って、O(logn) 時間で実行できることも理解しています。

ただし、クエリ時間が実際に O(logn) であることを証明することはできません。このリンク (および他の多くのリンク) は、各レベルで処理されるノードの最大数が 4 であることを証明できるため、O(4logn) == O(logn) であると述べています。しかし、おそらく矛盾によって、これをどのように証明するのでしょうか?

もしそうなら、より高次元の配列の範囲和にセグメント ツリーを使用するとしたら、証明はどのように拡張されるでしょうか?

たとえば、元の行列を 4 つの象限 (線形配列で間隔を半分にするのと同様) に分割して、象限セグメント ツリーを構築することで部分行列の合計を見つけることを考えることができますが、証明はわかりません。