具有 O(log(N)) 时间复杂度操作的 HashMap

Question

我在CodeSignal上进行了测试，但无法解决这个问题。

创建允许以下操作的数据结构。
insert xy - 插入一个带有键 x 和值 y 的对象。
get x - 返回带有键 x 的对象的值。
addToKey x - 将 x 添加到映射中的所有键
addToValue y - 将 y 添加到映射中的所有值。
每个操作的时间复杂度应该是O(log(N))

我能够使用 Java 中的数组和 LinkedList 制作哈希图。但我无法将时间复杂度提高到 O(log(N))。在我的实现中，插入和获取的时间复杂度为 O(1)（最坏情况下为 O(N)）。addToKey 和 addToValue 的时间复杂度是 O(N)，因为我必须迭代所有元素来修改键和值。
对于这个问题来说，合适的数据结构是什么？

Answer 1

在 The Vee 和 Tom Elias 的有用评论后进行编辑以更正答案。

您无法通过迭代所有元素来实现addToKeyand ，因为正如您所意识到的，这需要线性时间。addToValue

相反，您可以保留 akeyDelta和valueDelta int实例变量来保存应分别添加到每个键和值的值（或所有值的总和）。这是假设addToKey并且addToValue应该向键或值添加一个数值。

addToKey并且addToValue只需要更新那些实例变量，这将需要O(1).

该get(x)操作将搜索该键x - keyDelta并添加valueDelta到该键后返回其对应的值。

请注意，add(x,y)还需要进行更改，因为添加到 Map 的键值对不应受到先前对addToKey或 的调用的影响addToValue。insert(x,y)如果实际将该对插入x - keyDelta, y - valueDelta到地图中，则可以实现这一点。

如果使用 aTreeMap来实现键到值的映射，get则insert需要O(logN).