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.
Update query (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.
Code Implementation
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)
Update query (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.
Code Implementation
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;
// Adding children nodes
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)