1

範囲最小クエリ問題を解決するために作成されたセグメント ツリーにノードがいくつあるかを知りたいです。

また、ビルド操作にかかる時間とその理由は?

4

2 に答える 2

0

セグメント ツリーを使用する場合、ビルドは O(nlgn)、各クエリは O(lgn) です。

配列が静的な場合は、別のアルゴリズムRMQを試すこともできます。ビルド時間は O(nlgn) で、各クエリは O(1) のみです。

于 2013-01-18T09:22:39.770 に答える
0

セグメント ツリーの複雑さ:

  1. 要素を 1 つずつ初期化: O(NLogN)
  2. 配列からの初期化: O(N)
  3. クエリ範囲: O(logN)
  4. Insert(Update) 要素: O(logN)
于 2013-01-18T13:46:34.610 に答える