我想实现一个 DS，其中包含一组数字 {x0, x1, ... , xn}。
Init(n) - 设置数字 x0 = x1 = ... = xn = 0。O(n) 最坏情况。
Get(i) - 返回 xi 的值。 O(log n) 最坏情况。
Add(d, i, j) - 将值“d”添加到所有数字:xi , ... , xj (假设 i <= j)。 O(log n) 最坏情况。
我只想知道如何在上述时间复杂度内实现这些 DS。谢谢。
最佳答案
我将从构建一棵树开始，例如深度为 d 的完整二叉树，其中 2^d >= n >= 2^(d-1) 所以对于 5..8 个数字
g
e f
a b c d
1 2 3 4 5 6 7 8
现在将一个数字与每个叶子和每个内部节点相关联。
要提取一个值，将路径上的所有数字加在一起到叶子 - O(log n) 时间。
要将一个值添加到一个数字范围内，从顶部开始并将该值添加到其后代都在该范围内且其父节点有一些数字在该范围内和一些数字不在该范围内的节点。例如。添加到 3..7 添加到 b、c 和 7。最多应该有 O(log n) 个这样的数字，因为您不必在每个级别上更新两个以上的节点。
关于algorithm - 我可以使用哪些数据结构来满足下面提到的需求？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41156375/