# Segment Tree (Update) for Range Min Query and Range Sum Query

In the last post we discussed about constructing a segment tree and querying the segment tree. Time complexity of constructing a segment tree is O(n) and querying (RMQ) the segment tree is O(logn). Whereas space complexity of segment tree is O(n). As we need an array of size (2n-1) to construct a segment tree for an array of length n.

###### Updatequery (Range min query)

For update query, we are given an index which needs to be updated. Let val be the value needed to be changed of a given node x. We start from the root of the segment tree and update all nodes (containing minimum value from given index) which have given index in their range. If a node doesn’t have a given index in its range, we don’t make any changes to that node.

###### Construction of segment tree (Range min query)
//sb = segmentBegin
//se = segmentEnd

int construct (int arr[], int sb, int se, int si) {

//Base case (only 1 element)
if (sb == se) {
seg[si] = arr[sb];
} else {
int mid = (sb+se)/2; //Dividing given range in two equal halves

seg[si] = min((construct(arr, sb, mid, 2*si + 1)),
(construct(arr, mid+1, se, 2*si + 2)));
}

return seg[si];
}

###### Segment tree update (Range min query)
void update (int arr[], int sb, int se, int idx, int val, int i) {

//Base case: index not in the range
if (idx < sb || idx > se) {
return;
} else if (sb == se) {  //index to be changed
arr[idx] = val;
seg[i] = val;
} else {
int mid = (sb+se)/2;

if (idx >= sb && idx <= mid) {
update(arr, sb, mid, idx, val, 2*i + 1);
} else {
update(arr, mid+1, se, idx, val, 2*i + 2);
}

seg[i] = min(seg[2*i + 1], seg[2*i + 2]);
}

}

int getMin(int sb, int se, int x, int y, int i) {

//Base case: Out of bound range
if (sb > y || se < x) {
return INT_MAX;
} else if (sb >= x && se <= y) {
//Node in permissible range,
//send the value of internal node (i)
return seg[i];
} else {
int mid = (sb+se)/2;

//Checking children nodes
//[(2*i+1), (2*i+2)]
return min((getMin(sb, mid, x, y, 2*i + 1)),
(getMin(mid+1, se, x, y, 2*i + 2)));
}

}


Output

arr[] = {1, 3, 2, 7, 9, 11}

Minimum element in the range:
x = 1, y = 5: 2
x = 0, y = 3: 1
Update index 3, from 7 to 1
x = 2, y = 5: 1
Update index 0, from 1 to 5
x = 0, y = 2: 2

Here’s a working example: Range min query (Update)

###### Updatequery (Range sum query)

For update query, we are given an index which needs to be updated. Let diff be the difference in the new and previous value . We start from the root of the segment tree and update all nodes (containing sum from changed value) which have given index in their range.

###### Construction of segment tree (Range sum query)
//sb = segmentBegin
//se = segmentEnd

int construct (int arr[], int sb, int se, int si) {

if (sb == se) {
seg[si] = arr[sb];
} else {
int mid = (sb+se)/2;
seg[si] = ((construct(arr, sb, mid, 2*si + 1)) +
(construct(arr, mid+1, se, 2*si + 2)));
}

return seg[si];
}

###### Segment tree update (Range sum query)
void update (int sb, int se, int idx, int diff, int i) {

//Base case: index not in the range
if (idx < sb || idx > se) {
return;
}

seg[i] += diff;

if (sb != se) {
int mid = (sb+se)/2;
update(sb, mid, idx, diff, (2*i + 1));
update(mid+1, se, idx, diff, (2*i + 2));
}

}

int getSum(int sb, int se, int x, int y, int i) {

if (sb > y || se < x) {
return 0;
} else if (sb >= x && se <= y) {
//Node in permissible range,
//send the value of internal node (i)
return seg[i];
} else {
int mid = (sb+se)/2;

return (getSum(sb, mid, x, y, 2*i + 1) +
getSum(mid+1, se, x, y, 2*i + 2));
}

}


Output

arr[] = {1, 3, 2, 7, 9, 11}

Sum in the range:
x = 0, y = 2: 6
x = 3, y = 4: 16
Update index 3, from 7 to 1
x = 2, y = 5: 23
Update index 5, from 11 to 2
x = 3, y = 5: 12
x = 0, y = 5: 18

Here’s a working example: Range sum query (Update)