私は次のような問題を解決しようとしています（更新やクエリを含む）の範囲の重みk

Question

で項目の数を探す：

整数の重みを持つ項目の配列を考えると（任意の順序）、我々は持つことができます2つの可能な操作：

クエリ： の範囲xからyまでの重みkの項目の数を出力します。
更新：Vに一定 インデックスの項目の重みを変更

例：配列を指定

：[1,2,3,2,5,6,7,3 ]

を、我々は3に、インデックス1から重量2と項目数を照会した場合、我々は2の重みを持っているために、インデックス2の要素を変更した場合、答えは2

だろうし、我々は再度同じクエリを実行すると、答えは3になります。

これは確かにセグメントツリーの問題です（ポイントの更新を使用）。しかし、私はここで問題に直面している - 各セグメントは、1つのインデックスの答えを保持します。したがって、私は自分のセグメントツリーにベクトルを使わなければならないようです。しかし、これは事を過度に複雑にするでしょう。さらに、私はそれをどうやって行うのかもわかりません。

もっと良い解決策を教えてもらえますか？代わりに、セグメントツリーの

Answer 1

は、あなたがAVL、Treap、スプレイのように、二分探索木（BST）を使用してなど

1. 最初に、すべてが分離分探索木の値を登場のすべてのインデックスを格納する必要があります。

   BST 1：[0]、
   BST 2：[1,3]、
   あなたの例では、[1,2,3,2,5,6,7,3]、6分探索木があるはず BST 3：[2,7]、
   BST 5：[4]、
   BST 6：[5]、
   BST 7：[6]各クエリについて

2. （X、Y、K ）、SBT kの範囲[x、y]に入る要素の数を数えます。各更新量[X] = Vについて

3. は、BSTの重量[X]からXを削除し、BST vに

時間複雑さを追加x：O（nlogn + mlogn）nは長さでありますmは操作の数です。

空間の複雑さ：O（n）