-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRangeMinimumQuery.java
More file actions
133 lines (106 loc) · 3.68 KB
/
RangeMinimumQuery.java
File metadata and controls
133 lines (106 loc) · 3.68 KB
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
package com.problems;
import java.util.Arrays;
public class RangeMinimumQuery {
int[] segment;
int N; // length of original nums array
public RangeMinimumQuery(int[] nums){
// time to build the tree O(n)
N = nums.length;
int n = 1;
while(n < nums.length){
n *= 2;
}
segment = new int[2*n];
Arrays.fill(segment, Integer.MAX_VALUE);
for(int i = 0; i < N; i++){
segment[N + i] = nums[i];
}
for(int i = N -1; i > 0; i--){
segment[i] = Math.min(segment[2*i], segment[2*i+1]);
}
}
public void update(int index, int val){
// T(update) = O(logn)
segment[N +index] = val; // leaf node updated
/// update the internal node
int p = (N +index) / 2;
while (p != 0){
segment[p] = Math.min(segment[2*p], segment[2*p+1]);
p = p/2;
}
}
public int rangeMinQuery(int i, int j){
return helper(1, 1, N, i+1, j+1);
}
public int helper(int index, int l, int r, int ql, int qr){
// base case - leaf node
if(l == r){ // subarray of size 1
if(ql <= l && l <= qr){
return segment[index];
}else{
return Integer.MAX_VALUE;
}
}
// recursive
if(ql <= l && l <= r && r <= qr){
return segment[index];
}else if(qr < l || r < ql){ // no overlap
return Integer.MAX_VALUE;
}else{ // delegate
int mid = (l + r) / 2;
return Math.min(helper(2 * index, l, mid, ql, qr),
helper(2 * index + 1, mid + 1, r, ql, qr));
}
}
public int rangeMinQueryIterative(int i, int j){
int L = N + i; // leftmost leaf in the segment tree
int R = N + j; // rightmost leaf in the segment tree
int ans = Integer.MAX_VALUE;
while(L <= R){
if(L % 2 == 1){ //L is odd, right child
ans = Math.min(ans, segment[L]);
L = L/2 + 1;
}else{
L = L/2;
}
if(R %2 == 0){
ans = Math.min(ans, segment[R]);
R = R/2 - 1;
}else{
R = R/2;
}
}
return ans;
}
//...
public void constructTree(int[] input, int[] segTree, int low, int high, int position){
if(low == high){
segTree[position] = input[low];
return;
}
int mid = (low + high) / 2;
constructTree(input, segTree, mid + 1, high, 2*position + 1);
constructTree(input, segTree, mid + 1, high, 2*position + 2);
segTree[position] = Math.min(segTree[2*position + 1], segTree[2*position + 2]);
}
public int rangeMinQuery(int[] segmentTree, int qlow, int qhigh, int low, int high, int pos){
if(qlow <= low && qhigh >= high){
return segmentTree[pos];
}
if(qlow > high || qhigh < low){
return Integer.MAX_VALUE;
}
int mid = (low + high) / 2;
return Math.min(rangeMinQuery(segmentTree, qlow, qhigh, low, mid, 2*pos + 1),
rangeMinQuery(segmentTree, qlow, qhigh, mid + 1, high, 2*pos + 2));
}
}
class TDRSQ{
public static void main(String[] args) {
RangeMinimumQuery rmq = new RangeMinimumQuery(new int[]{5,8,6,3,1,7,2,6});
//RangeMinimumQuery rmq = new RangeMinimumQuery(new int[]{5,8,6,3,1,7,2});
System.out.println(Arrays.toString(rmq.segment) + " " + rmq.N + " " + rmq.segment.length);
System.out.println(rmq.rangeMinQuery(1,2));
System.out.println(rmq.rangeMinQueryIterative(1,3));
}
}