0

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

PS n 不是 2 的倍数（我不知道这是否会影响解决方案） 

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);
    }
}


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

4

1 回答 1

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.
}

Also you are wasting a lot of tree space while building and updating the tree. To avoid extra space usage, use 2*j and 2*j+1 as the child of current node j. Implementation should be something like this:

update(i, k, 2*j, from, mid);
update(i, k, 2*j+1, mid+1, to);
于 2016-09-28T04:37:57.313 回答