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.

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 
Following is the implementation of segment tree (Range min query)

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 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(sb, mid, idx, val, 2*i + 1);
    } else {
      update(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;
   return min((getMin(sb, mid, x, y, 2*i + 1)),        // Checking children nodes 
                       (getMin(mid+1, se, x, y, 2*i + 2)));  // [(2*i+1), (2*i+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 
Following is the implementation of segment tree (Range sum query)

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) {
    return seg[i];   //Node in permissible range, send the value of internal node (i)
  } else {
    int mid = (sb+se)/2;
    return getSum(sb, mid, x, y, 2*i + 1) +             // Adding children nodes
                       getSum(mid+1, se, x, y, 2*i + 2);
    }

}

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

Leave a Reply

Your email address will not be published.