問題タブ [segment-tree]

私はセグメント ツリーにまったく慣れていないので、セグメント ツリーをもう少し練習して忙しくしたいと思っています。

問題は実際にはより ACM に似ており、次の条件があります: n 個の数値と m 個の操作があり、n,m<=10,000、各操作は次のいずれかです: 1. 数値 x を引いて間隔を更新します。x は異なる場合があります。毎回 2. 間隔を照会して、間隔内の数値が <= 0 である数を見つけます。

セグメント ツリーの構築とここでの更新は明らかに O(nlog n) / O(log n) で実行できますが、O(log n) でクエリを作成する方法がわかりません。誰か提案やヒントを教えてもらえますか? どんな提案も役に立ちます！ありがとう！

TL;DR:

n 個の数値と 2 つの型の操作が与えられた場合:

1. [a,b] のすべての要素に x を追加します。x は毎回異なる場合があります
2. [a,b] の要素数のクエリは < C です。C には定数が指定されています

操作1と2の両方をO(log n)で実行できるようにする方法は?

指定された配列から最大合計連続部分配列を見つけたかったのです。Kadane のアルゴリズムを使用した動的計画法の概念を使用して、最大和連続部分配列アプローチを見つける O(n) アプローチを知っています。

ただし、範囲クエリの数が非常に多い場合は、多くの時間がかかります。O（log（n））時間で解決する範囲クエリに回答するのに最適なオプションであるため、セグメントツリーを使用して解決する方法はありますか。ありがとうございました。

BIT の仕組みを知っています。しかし、ビットを使用して完全な範囲内の最小/最大要素を見つけることができるか、より具体的には、すべての更新プロセスが完了した後に最小 (または最大) 値を見つけることができるかどうか疑問に思っていました。これはセグメント ツリーを使用して非常にうまく達成できることはわかっていますが、BIT を使用して同じことを行うことは可能ですか?

ありがとう。

PS: 完全な BIT をトラバースし、各インデックスの値を計算する明白な方法を知っています。より効率的/最適化された方法を探しています。

a[]lengthのソートされていない整数配列があるとしNます。a[i]-a[j]ここで、指定された間隔( )内で k 番目に小さい整数を見つけたいと考えています1 <= i <= j <= N。例: 配列がありa[10]={10,15,3,8,17,11,9,25,38,29}ます。a[2]-a[7]今度は、間隔内で 3 番目に小さい要素を見つけたいと思います。答えは 9 です。これは、その間隔をソートすることで実行できることがわかっています。しかし、これにはO(Mlog(M))( M = j - i + 1) 時間がかかります。また、これはセグメントツリーで実行できることは知っていますが、そのようなクエリを処理するためにそれを変更する方法がわかりません。

与えられた N*N 行列と、同じ与えられた行列に対する Q クエリ。各クエリの形式は x1、y1、x2、y2 です。それぞれ左上隅と右下隅として (x1,y1) と (x2,y2) で定義されるサブマトリックス内の個別の要素の数を見つける必要があります。制約: N<=300 Q<=10^5 クエリごとにサブマトリックスを反復処理する単純なアプローチを使用しています。より良いアプローチはありますか？

私はBITに関するさまざまなチュートリアルを読みました..トップコーダーなどのチュートリアルで、すべての操作はそれらで十分に説明されていますが、BITの作成方法がわかりません.

1-D の配列が与えられた場合、対応する BIT をどのように計算する必要があるでしょうか? 元。配列が 10 8 5 9 1 の場合、これの BIT は何になりますか?

私は初心者なので、私の質問がばかげているように聞こえる場合は申し訳ありませんが、これを理解していません。だから、助けてください。

私はspojでこの問題を試していました。www.spoj.com/problems/RRANGE.セグメント ツリーが必要です。しかし、問題は配列のサイズにあります。ここでは (1 <= N <= 1,000,000,000)。これが私の実装です（ほぼN <1000000で正しい答えが得られます）

この CodeChef の問題を解決しようとしています:

テーブルには N 個のコインがあり、0 から N - 1 までの番号が付けられています。
次の 2 種類の操作を実行する必要があります。

1. A から B までの番号のコインをすべて裏返します。これは、コマンド「0 A B」で表されます。

2. A から B までの番号のコインのうち、表が何枚あるか答えてください。これは、コマンド「1 A B」で表されます。

入力: 最初の行には 2 つの整数 N と Q が含まれます。次の Q 行はそれぞれ、前述のように "0 A B" または "1 A B" のいずれかの形式です。

出力: 対応するクエリに必要な回答を含む「1 A B」形式のクエリごとに 1 行を出力します。

私が使用したのはセグメントツリーです。そのため、ユーザーがタイプ 1 AB のクエリを入力するたびに、出力はその間隔 [A,B] での合計になります。ただし、Time Limit Exceeded エラーが発生します。エラーは更新ステップ 0 A B が原因だと思います。配列内の要素を更新した後、ツリーを再構築します。コードを以下に示します。誰かがより迅速に更新する方法を教えてくれますか?

ところで-サンプル入力に必要な出力を取得しています。

編集：

GeeksForGeeks によると、ツリーの構築コストは O(n) で、更新方法は O(log n) です。したがって、更新のための新しいメソッドは次のとおりです。

そして、main メソッドの if ループが次のように変更されました。

しかし、それでも TLE エラーが発生します。

私は最近、セグメント ツリーの遅延伝播について読み、それもコーディングしました。助けてください

私の更新機能は次のとおりです。