查找範圍與體重k個項目的數量（含更新和查詢）

Question

我試圖解決以下問題：

考慮到與整型權（任意順序）項目的數組，我們可以有2個可能的操作：

查詢：輸出是權重k的項，在 範圍x到y的數量。
更新：在一定的 索引換物品的重量到v

例：

鑑於數組：[1,2,3,2,5,6,7,3 ]

如果我們查詢從索引1與權重2項至3的數，則答案是2.

如果我們在索引2修改元件以具有2的權重，那麼我們再次進行相同的查詢，答案將是3.

這當然是（用點更新）段樹問題。但是，我在這裏面臨一個問題 - 每個細分市場只會爲1個指數提供答案。因此，我似乎必須在分段樹中使用向量。但這會讓事情變得複雜。此外，我不知道該怎麼做。

是否有人能夠告訴我一個更好的解決方案？

Answer 1

相反段樹，你應該使用二叉搜索樹（BST），像AVL，樹堆，擴張和等

1. 起初，存儲所有的指標都在分離BSTS出現值。在你的例子[1,2,3,2,5,6,7,3]，應該有6個BSTS：

   BST 1：[0]，
   BST 2：[1,3]，
   BST 3：[2,7]，
   BST 5：[4]，
   BST 6：[5]，
   BST 7：[6]

2. 對於每個查詢（X，Y，K ），請計算SBT k中落入範圍[x，y]的元素數。

3. 對於每一更新重量[X] = V，從BST重量[X]刪除x和添加x到BST v

時間複雜度：O（nlogn + mlogn），其中n是長度的數據，m是操作的數量。 （n）