algorithm - 在 O(n) 中创建二叉树

Question

我有一个带有 n 个数字的序列，我想创建一个数据结构来回答以下问题：n = [5 ,7, 4, 24, 8, 3, 12, 34] 我想要的序列min(2,5)然后答案是 3，因为a2=7, a3=4, a4=24, a5=8. 所以 min(i,j) 返回 (i,j) 之间最小数的位置。我认为保存这个序列的一个好的数据结构是一个完整的二叉树来保存叶子的序列号。但是我怎样才能在 O(n) 中实现这个结构呢？

标签： algorithmdata-structurestreebinary-tree

Answer 1

您只需要一个具有范围最小查询的段树。这是它的详细解释。构建时间为O(n)，因为树中的节点数不超过2 * n，所以最终的时间复杂度为O(n)。

如果您不仅需要找到最小值，还需要找到位置，那么在顶点内部，您不仅需要存储最小值，还需要存储达到的位置。如何更新这样的结构似乎很清楚：当你重新计算父亲中的最小值时，你需要查看它是从哪个儿子接收的，并从儿子那里取最小值的对应位置。对于叶子，位置等于叶子本身的位置。