给定一个数字，比如'KEY'和map <int,>关联。我试图找到一个最小的键k(条件:k <</p>
的例子:
map <int, int> myMap = {{3,1}, {4,3}, {5,2}, {6,3}, {7,2}, {8,5}};
// ^^^
int KEY = 7;
的答案是4，因为对于所有小于7(KEY)的键，键4和键6的最大值为3。4是最小的键
映射动态增长，有几个这样的查询与KEY。
我试图在O(logN)时间内得到{k,v}对
我使用lower_bound后卡住了。使用下界可以得到k的最大值，使得k <关键。在上面的示例中，我能够为KEY>
更新:
我确保在对数时间内对地图进行更新。整数不能超过10^5。是否有可能使用一些其他的数据结构和方法(在这种情况下，它看起来像动态规划/二进制搜索)来解决这个对数时间?
这个怎么样?您维护一个次要映射，它是主映射的子集。具体来说，当且仅当主映射中所有较小的键对应于较小的值时，该副映射将包含{k, v}。
对于您的{3,1}, {4,3}, {5,2}, {6,3}, {7,2}, {8,5}示例，此次要映射将是{3,1}, {4,3}, {8,5}。观察值是如何随着键单调增加的。
如何使用这个映射来回答这个问题应该是显而易见的-只需用lower_bound查找键。在本例中，对于键7，查找将找到正确答案4。
现在，如何维护这个映射。当您将{k, v}插入到主映射中时，使用lower_bound在辅助映射中查找k。有两种可能:
-
存在一个小于等于或大于等于值的键。什么都不做，二级映射不需要更新。
-
没有更小的键，或者更小的键对应更小的值。
- 将
{k, v}插入辅助映射 - 按顺序遍历键，从
k开始，直到遇到值较大的键k'，或到达结束。擦除k和k'之间的范围(不包括两者)，或从k(不包括)到末尾。
- 将
表面上，最后一步看起来是线性的但实际上它是平摊常数。在N插入中，这一步最多只能遍历2*N个元素(例如，N-1的第一步每个插入一个元素，最后一步删除它们并插入一个元素)。
是否有任何数据结构可以帮助我在logN时间内实现此目标?
除非您能够以有意义的方式组合这些值，否则不会。所有(几乎)log N算法都依赖于分而治之的方法。
你基本上有两个不相关的序列。通过tree映射的键允许你做log N的事情但是你需要在一个非结构化序列上进行另一次搜索这是O(N)
因此，要在O(log N)上完成此操作，您需要以某种方式将键和值结合起来，或者按照@Igor建议的路由注释，这实际上是映射的映射。
当然，调整实现可能会带来好处，但不是O(N) ->O(log N)类型的优势