更新线段树中的一项

Question

我正在解决的部分问题涉及获取数组范围 (RMQ) 中的最小值，因此我实现了一个线段树，到目前为止它运行良好。然后我想更新原始数组中的一项（没有超过一项的更新）并在线段树中更新它。到目前为止，我所做的是从上到下遍历线段树，直到到达叶子为止，但这似乎存在一些错误。这是代码的更新部分，那里似乎有什么问题？

P.S。 n 不是二的倍数（不知道会不会影响解法）

public void update(int i, int k) {
    update(i, k, 0, 0, n - 1);
}
/// <summary>
/// update one item in the segment tree
/// </summary>
/// <param name="i">The index of the element to be updated in the original array</param>
/// <param name="k">The new value</param>
/// <param name="j">The current index in the segment tree</param>
/// <param name="from">range start index (inclusive)</param>
/// <param name="to">range end index (inclusive)</param>
private void update(int i, int k, int j, int from, int to) {
    tree[j] = Math.Min(tree[j], k);
    if (from == to) return;

    int mid = from + (to - from) / 2;

    if (from <= i && mid >= i) {
        update(i, k, 2 * j + 1, from, mid);
    } else {
        update(i, k, 2 * j + 2, mid + 1, to);
    }
}

P.S。问题的其他部分可能有一些bug，但似乎这是最有可能出现bug的部分。

Answer 1

您的更新函数没有正确设置和构建线段树中的更新值。

private void update(int i, int k, int j, int from, int to) {

    if (from == to) {
        tree[j] = k; //set the new leaf value.
        return;
    }

    int mid = (from+to)/2;

    if (from <= i && mid >= i) {
        update(i, k, 2 * j + 1, from, mid);
    } else {
        update(i, k, 2 * j + 2, mid + 1, to);
    }
    tree[j] = Math.Min(tree[2*j+1], tree[2*j+2]); //keep correcting minimums for every parents with the current minimum.
}

此外，您在构建和更新树时浪费了很多树 space。为避免额外使用 space，请使用 2*j 和 2*j+1 作为当前节点 j 的子节点。实现应该是这样的：

update(i, k, 2*j, from, mid);
update(i, k, 2*j+1, mid+1, to);

更新线段树中的一项

Update one item in segment tree

c#

algorithm

segment-tree

rmq