2

データ構造からテストのトレーニングを行っていますが、この問題を解決できません。

シーケンスa_1、...、a_nを保持し、2つの操作を実行できるデータ構造を設計します。

  1. a_iを値xに設定します
  2. 2つのインデックスiとjの間のシーケンスで値xが発生する回数をカウントします。私が明確にしたことを確認するために（私は英語が苦手です）、それは|{a_k: a_k = x and i <= k <= j}|与えられたx、i、jに戻ることを意味します。

制約：

  • a_iは区間[0、...、10 ^ 9]からのものであり、
  • nは小さい-10^5未満

両方の操作は、最大でO（log n）時間で機能するはずです。私がそれを見る唯一の方法は、残念ながら、O（log ^ 2 n）です。区間木をmaps<int,int>ノード内に保持します。これは、サブツリーでxが発生する回数をカウントします。また、0回発生する値をマップに保持しないことも重要です（メモリの複雑さ）。

どうすればもっとうまく解決できますか？誰か助けてもらえますか？

4

1 に答える 1

6

これは、2 つのデータ フィールドを持つ BST です。

BSTNode<E>{
   int index;
   E value;
   BSTNode left, right;
}

検索が O(lg n): になるように、インデックスでツリーを並べ替えます。これは、挿入と設定 ( seta_i to value x) に役立ちます。

にcount how many times value x occurs in a sequence between two indexes: i, j

編集：

iとの共通の親を見つけた後j、サブツリーをトラバースする代わりに、単純に値の頻度を調べることができます: 各ノード (ここでは commonParent) は頻度マップを持つことができます: Map<E,Integer> childrenFreq = new HashMap<E,Integer>(). 共通の親が O(lg n) で見つかると、これは O(1) になります。

于 2012-12-31T17:03:42.260 に答える