Range Minimum Query - Segment Tree (Java)
Given an array, there is a popular problem to search the minimum value in a range [a, b]. This is called Range Minimum Query. This post describes a method to solve the range minimum query problem using Segment Tree.
The basic idea of a Segment tree is as follows:
Given an array A with size n: the index of the array looks like this [0, 1, 2, ...., n-1],
- The root of the Tree contains the minimum value of the whole array, or the minimum value in the range
[0, n - 1]. - Then the
left childof the root contains the minimum value of the left half part of the array: the minimum value in therange [0, mid], - The
Right childof the root contains the minimum value of the right half part of the array: the minimum value in the range[mid + 1, n-1],
where mid = (0 + n -1 ) / 2.
In other worlds:
|
1 2 3 4 5 |
Tree(root) = min(0, n - 1) Tree(root.left) = min(0, (n - 1) / 2) Tree(root.right) = min((n-1)/2 + 1, n-1) |
Apparently, we can build the tree recursively. The pseudo code is as following:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int buildTree(int root, int[] Tree, int start, int end, int[] A) { if (start == end) { Tree[root] = A[start]; return Tree[root]; } int mid = start + (end - start) / 2; int leftMin = buildTree(root * 2 + 1, Tree, start, mid, A); int rightMin = buildTree(root * 2 + 2, Tree, mid + 1, end, A); Tree[root] = min(leftMin, rightMin); return Tree[root]; } |
How can we use the tree to do range minimum query:
We start from the root of the tree: range(root = 0, start = 0, end = n - 1, qstart, qend)
- if [
start, end] is in the range of the query[qstart, qend], we immediately know thatTree[root]is the answer. - If the query range
[qstart, qend]is in the range of[start, end], we can search the left tree and right tree, then return theminimum value. - If there is no overlapping, we return
Integer.Maxvalue.
The pseudo code looks like this:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int rangeQUtil(int root, int[] Tree, int start, int end, int qs, int qe) { if (qs <= start && end <= qe) { return Tree[root]; } if (qs > end || qe < start) { return Integer.MAX_VALUE; } int mid = start + (end - start) / 2; int leftMin = rangeQUtil(root * 2 + 1, Tree, start, mid, qs, qe); int rightMin = rangeQUtil(root * 2 + 2, Tree, mid + 1, end, qs, qe); return min(leftMin, rightMin); } |
The following is the code with test:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
import java.util.LinkedList; import java.util.Queue; public class SegmentTree { int[] data; public SegmentTree(int n) { data = new int[n]; } int getMin(int a, int b) { if (a < b) return a; else return b; } int build(int root, int left, int right, int[] input) { if (left == right) { data[root] = input[left]; return data[root]; } int mid = left + (right - left) / 2; int leftMin = build(2 * root + 1, left, mid, input); int rightMin = build(2 * root + 2, mid + 1, right, input); data[root] = getMin(leftMin, rightMin); return data[root]; } static SegmentTree build(int[] input){ SegmentTree st = new SegmentTree(2 * input.length + 1); st.build(0, 0, input.length - 1, input); return st; } int rangeMin(int qStart, int qEnd, int n){ return rangMinUtil(0, 0, n, qStart, qEnd, data); } int rangMinUtil(int root, int start, int end, int qStart, int qEnd, int[] input){ if (qEnd < start) { return Integer.MAX_VALUE; } if (qStart > end) { return Integer.MAX_VALUE; } if (start >= qStart && end <= qEnd) { return data[root]; } int mid = start + (end - start) / 2; int leftMin = rangMinUtil(2*root + 1, start, mid, qStart, qEnd, input); int rightMin = rangMinUtil(2 * root + 2, mid + 1, end, qStart, qEnd, input); return getMin(leftMin, rightMin); } void treeString(int root) { } void printTree(){ int root = 0; Queue<Integer> first = new LinkedList<>(); Queue<Integer> second = new LinkedList<>(); first.add(root); StringBuffer sb = new StringBuffer(); while (!first.isEmpty()) { second = new LinkedList<>(); while(!first.isEmpty()) { int cur = first.poll(); sb.append(cur + "\t"); int left = 2 * cur + 1; int right = 2 * cur + 2; if (left < data.length) { second.add(left); } if(right < data.length) { second.add(right); } } sb.append("\n"); first = second; } System.out.println(sb); } void print(int start, int end, int n){ int min = rangeMin(start, end, n); System.out.println("min is " + min); } public static void main(String[] args) { int[] a = new int[]{0,1,2,3,4,5}; SegmentTree st = SegmentTree.build(a); st.print(0,4, a.length - 1); st.print(2,4, a.length - 1); st.print(4,5, a.length - 1); st.print(5,5, a.length - 1); } } |
Reference:
