当前位置: 动力学知识库 > 问答 > 编程问答 >

c# - Update one item in segment tree

问题描述:

A part of a problem I'm solving involves getting the minimum in a range of an array (RMQ), so I implemented a segment tree and it works fine so far. Then I want to update one item in the original array (There are no updates with more than one) and update it in the segment tree. What I do so far is traverse the segment tree from top to bottom till I reach the leaves, but there seems to be some bug in this. Here is the update part of the code, what seems to be wrong there ?



P.S. n is not a multiple of two ( I don't know if this affects the solution )



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. There are other parts of the problem that may have some bugs, but it seems that this is the part most likely to have the bug.

网友答案:

Your update function doesn't set and build up the updated values in the segment tree correctly.

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);
分享给朋友:
您可能感兴趣的文章:
随机阅读: