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

Top