1 // Copyright 2010-2021 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 // We use the notation min(arr, i, j) for the minimum arr[x] such that i <= x
15 // and x < j.
16 // Range Minimum Query (RMQ) is a data structure preprocessing an array arr so
17 // that querying min(arr, i, j) takes O(1) time. The preprocessing takes
18 // O(n*log(n)) time and memory.
19
20 // Note: There exists an O(n) preprocessing algorithm, but it is considerably
21 // more involved and the hidden constants behind it are much higher.
22 //
23 // The algorithms are well explained in Wikipedia:
24 // https://en.wikipedia.org/wiki/Range_minimum_query.
25 //
26 //
27 // Implementation: The idea is to cache every min(arr, i, j) where j - i is a
28 // power of two, i.e. j = i + 2^k for some k. Provided this information, we can
29 // answer all queries in O(1): given a pair (i, j) find the maximum k such that
30 // i + 2^k < j and note that
31 // std::min(min(arr, i, i+2^k), min(arr, j-2^k, j)) = min(arr, i, j).
32
33 #ifndef OR_TOOLS_UTIL_RANGE_MINIMUM_QUERY_H_
34 #define OR_TOOLS_UTIL_RANGE_MINIMUM_QUERY_H_
35
36 #include <algorithm>
37 #include <functional>
38 #include <numeric>
39 #include <utility>
40 #include <vector>
41
42 #include "ortools/util/bitset.h"
43
44 namespace operations_research {
45 template <typename T, typename Compare = std::less<T>>
46 class RangeMinimumQuery {
47 public:
48 explicit RangeMinimumQuery(std::vector<T> array);
49 RangeMinimumQuery(std::vector<T> array, Compare cmp);
50
51 // Returns the minimum (w.r.t. Compare) arr[x], where x is contained in
52 // [from, to).
53 T GetMinimumFromRange(int from, int to) const;
54
55 const std::vector<T>& array() const;
56
57 private:
58 // cache_[k][i] = min(arr, i, i+2^k).
59 std::vector<std::vector<T>> cache_;
60 Compare cmp_;
61
62 DISALLOW_COPY_AND_ASSIGN(RangeMinimumQuery);
63 };
64
65 // RangeMinimumIndexQuery is similar to RangeMinimumQuery, but
66 // GetMinimumIndexFromRange returns the index for which the minimum is attained.
67 template <typename T, typename Compare = std::less<T>>
68 class RangeMinimumIndexQuery {
69 public:
70 explicit RangeMinimumIndexQuery(std::vector<T> array);
71 RangeMinimumIndexQuery(std::vector<T> array, Compare cmp);
72
73 // Returns an index idx from [from, to) such that arr[idx] is the minimum
74 // value of arr over the interval [from, to).
75 int GetMinimumIndexFromRange(int from, int to) const;
76
77 // Returns the original array.
78 const std::vector<T>& array() const;
79
80 private:
81 // Returns a vector with values 0, 1, ... n - 1 for a given n.
82 static std::vector<int> CreateIndexVector(int n);
83 struct IndexComparator {
84 bool operator()(int lhs_idx, int rhs_idx) const;
85 const std::vector<T> array;
86 Compare cmp;
87 } cmp_;
88 const RangeMinimumQuery<int, IndexComparator> rmq_;
89 DISALLOW_COPY_AND_ASSIGN(RangeMinimumIndexQuery);
90 };
91
92 // RangeMinimumQuery implementation
93 template <typename T, typename Compare>
RangeMinimumQuery(std::vector<T> array)94 inline RangeMinimumQuery<T, Compare>::RangeMinimumQuery(std::vector<T> array)
95 : RangeMinimumQuery(std::move(array), Compare()) {}
96
97 // Reminder: The task is to fill cache_ so that
98 // cache_[k][i] = min(arr, i, i+2^k) for every k <= Log2(n) and i <= n-2^k.
99 // Note that cache_[k+1][i] = min(cache_[k][i], cache_[k][i+2^k]), hence every
100 // row can be efficiently computed from the previous.
101 template <typename T, typename Compare>
RangeMinimumQuery(std::vector<T> array,Compare cmp)102 RangeMinimumQuery<T, Compare>::RangeMinimumQuery(std::vector<T> array,
103 Compare cmp)
104 : cache_(MostSignificantBitPosition32(array.size()) + 1),
105 cmp_(std::move(cmp)) {
106 const int array_size = array.size();
107 cache_[0] = std::move(array);
108 for (int row_idx = 1; row_idx < cache_.size(); ++row_idx) {
109 const int row_length = array_size - (1 << row_idx) + 1;
110 const int window = 1 << (row_idx - 1);
111 cache_[row_idx].resize(row_length);
112 for (int col_idx = 0; col_idx < row_length; ++col_idx) {
113 cache_[row_idx][col_idx] =
114 std::min(cache_[row_idx - 1][col_idx],
115 cache_[row_idx - 1][col_idx + window], cmp_);
116 }
117 }
118 }
119
120 template <typename T, typename Compare>
GetMinimumFromRange(int from,int to)121 inline T RangeMinimumQuery<T, Compare>::GetMinimumFromRange(int from,
122 int to) const {
123 DCHECK_LE(0, from);
124 DCHECK_LT(from, to);
125 DCHECK_LE(to, array().size());
126 const int log_diff = MostSignificantBitPosition32(to - from);
127 const int window = 1 << log_diff;
128 const std::vector<T>& row = cache_[log_diff];
129 return std::min(row[from], row[to - window], cmp_);
130 }
131
132 template <typename T, typename Compare>
array()133 inline const std::vector<T>& RangeMinimumQuery<T, Compare>::array() const {
134 return cache_[0];
135 }
136
137 // RangeMinimumIndexQuery implementation
138 template <typename T, typename Compare>
RangeMinimumIndexQuery(std::vector<T> array)139 inline RangeMinimumIndexQuery<T, Compare>::RangeMinimumIndexQuery(
140 std::vector<T> array)
141 : RangeMinimumIndexQuery(std::move(array), Compare()) {}
142
143 template <typename T, typename Compare>
RangeMinimumIndexQuery(std::vector<T> array,Compare cmp)144 RangeMinimumIndexQuery<T, Compare>::RangeMinimumIndexQuery(std::vector<T> array,
145 Compare cmp)
146 : cmp_({std::move(array), std::move(cmp)}),
147 rmq_(CreateIndexVector(cmp_.array.size()), cmp_) {}
148
149 template <typename T, typename Compare>
GetMinimumIndexFromRange(int from,int to)150 inline int RangeMinimumIndexQuery<T, Compare>::GetMinimumIndexFromRange(
151 int from, int to) const {
152 return rmq_.GetMinimumFromRange(from, to);
153 }
154
155 template <typename T, typename Compare>
operator()156 inline bool RangeMinimumIndexQuery<T, Compare>::IndexComparator::operator()(
157 int lhs_idx, int rhs_idx) const {
158 return cmp(array[lhs_idx], array[rhs_idx]);
159 }
160
161 template <typename T, typename Compare>
CreateIndexVector(int n)162 std::vector<int> RangeMinimumIndexQuery<T, Compare>::CreateIndexVector(int n) {
163 std::vector<int> result(n, 0);
164 std::iota(result.begin(), result.end(), 0);
165 return result;
166 }
167
168 template <typename T, typename Compare>
array()169 inline const std::vector<T>& RangeMinimumIndexQuery<T, Compare>::array() const {
170 return cmp_.array;
171 }
172 } // namespace operations_research
173 #endif // OR_TOOLS_UTIL_RANGE_MINIMUM_QUERY_H_
174