Segment Tree Range Minimum Query

Problem:

Give an array, what is the minimum/maximum/sum in range [i, j]

LeetCode 307

Alternative solutions:

• Brute Force: $$O(mn)$$ m queries, with n size range.

• DP: hold a matrix m[i,j] = the minimum in range [i, j]

  • $$O(n^2)$$ build and update
  • answer query in $$O(1)$$

Solution: segment tree

• Time complexity:
  • build: $$O(n)$$
  • query: $$O(logn)$$ in worst case 4logn
• Space complexity: $$O(n)$$ in worst case: 4n
• GeeksForGeeks
• video

1. partial overlap: search both sides
2. total overlap: return root val
3. no overlap: return max

Example:

query [2,4]:

partial overlap [0,5]
partial overlap [0,2]
no overlap [0,1], return max
total overlap [2,2], return 4, min(-1, 4) = 4
partial overlap [3,5]
total overlap [3,4], return 0
no overlap [5,5] return max
min(max, 0) = 0;
min(0, 4) = 0;

query [0,4]:

partial overlap [0,5]
total overlap [0,2], return -1;
partial overlap [3,5]
total overlap [3,4], return 0
no overlap [5,5] return max
min(max, 0) = 0;
min(0, -1) = -1;

Build the Segment Tree:

size: find the power of 2 which is closest to the size of the array length

len = 4, 4*2-1 = 7
len = 5, 8*2-1 = 15

In worst case, the size of the array is 4n, so the time to build the array is $$O(n)$$.

ith child: 2i+1, 2i+2

ith parent: (i-1)/2

Code:

pos: the root of the tree

void constructTree(int input[], int segTree[], int low, int high, int pos) {
    if (low == high) {
        segTree[pos] = input[low];
        return;
    }
    int mid = (low+high)/2;
    constructTree(input, segTree, low, mid, 2*pos+1); // left child
    constructTree(input, segTree, mid+1, high, 2*pos+2); // right child
    segTree[pos] = min(segTree[2*pos+1], segTree[2*pos+2]);
}

int rangeMinQuery(int segTree[], int qlow, int qhigh, int low, int high, int pos) {
    if (qlow <= low && qhigh >= high) { // total overlap
        return segTree[pos];
    }    
    if (qlow > high || qhigh < low) { // no overlap
        return INT_MAX;
    }
    int mid = (low+high)/2;
    return min(rangeMinQuery(segTree, qlow, qhigh, low, mid, 2*pos+1),
               rangeMinQuery(segTree, qlow, qhigh, mid+1, high, 2*pos+2));
}

Update a value:

Like tree construction and query operations, update can also be done recursively. We are given an index which needs to updated. Let diff be the value to be added. We start from root of the segment tree, and add diff to all nodes which have given index in their range. If a node doesn’t have given index in its range, we don’t make any changes to that node.

void updateTree(int i, int diff, int low, int high, int pos) {
    if (i < low || i > high) { // not in range
        return;
    }
    // i is in range, update the value
    segTree[pos] += diff;
    if (low == high) return;
    int mid = (low+high)/2;
    updateTree(i, diff, low, mid, 2*pos+1);
    updateTree(i, diff, mid+1, high, 2*pos+2);
}