Range Minimum Query
Given an array 
![A[m] = min_{i<k<j}\{A[k]\}](https://s0.wp.com/latex.php?latex=A%5Bm%5D+%3D+min_%7Bi%3Ck%3Cj%7D%5C%7BA%5Bk%5D%5C%7D+&bg=ffffff&fg=333333&s=0&c=20201002)
There are many ways to do this. In the case where
Segment Trees
The idea behind a segment tree is to build a binary tree where each node represents a segment of 
Now, how are nodes and segments assigned? For simplicity, let’s assume that
- Starting at the lowest level of the tree, we’ll have
. As shown in the following figure, if we label leaf nodes from
to
from left to right, each node
will contain the value
- For each internal node
starting from the bottom, we compute
as follows:
. Meaning, a parent node
is minimum.
- Since this is a binary tree with the last level having
. Level
. This means that each node on a level
will represent a segment of length
.
The implementation is going to be straight forward from here on. We’ll represent the tree as an array tree of length 2 << ceil(log2(N + 1)). Node i has a left child 2 * i and a right child 2 * i + 1. On an update(i), we’ll traverse the tree from top to bottom, change array value at when we reach the leaf i, and update the tree as we go back up. On a getMin(range), we’ll recurse from root until we visit all maximal sub-segments of the range and return the required value. Here’s an implementation in C++ with this tutorial as a reference:
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
class segTree {
// O(n)
int *array, *tree;
int arrayLen, treeLen;
// O(n)
void initialize(int node, int b, int e) {
if (b == e)
tree[node] = b;
else {
// recurse
initialize(2 * node, b, (b + e) / 2);
initialize(2 * node + 1, (b + e) / 2 + 1, e);
// update value
if (array[tree[2 * node]] <= array[tree[2 * node + 1]])
tree[node] = tree[2 * node];
else
tree[node] = tree[2 * node + 1];
}
}
public:
segTree(int *array, int arrayLen) {
this->arrayLen = arrayLen;
this->array = array;
this->treeLen = 2 << (int)ceil(log2(arrayLen));
cout << "treeLen=" << treeLen << endl;
this->tree = new int[treeLen];
memset(tree, -1, sizeof(int) * treeLen);
initialize(1, 0, arrayLen - 1);
}
// O(log n)
void update(int i, int v, int node = 1, int b = 0, int e = 0) {
e = arrayLen - 1 - e;
if (b == e) {
array[i] = v;
} else {
int mid = (b + e) / 2;
if (i <= mid)
update(i, v, 2 * node, b, arrayLen - 1 - mid);
else
update(i, v, 2 * node + 1, mid + 1, arrayLen - 1 - e);
if (array[tree[2 * node]] <= array[tree[2 * node + 1]])
tree[node] = tree[2 * node];
else
tree[node] = tree[2 * node + 1];
}
}
// O(log n)
int query(int i, int j, int node = 1, int b = 0, int e = 0) {
e = arrayLen - 1 - e;
// bad interval
if (i > e || j < b)
return -1;
// good interval
if (b >= i && e <= j)
return tree[node];
// partial interval
int left = query(i, j, 2 * node, b, arrayLen - 1 - (b + e) / 2);
int right = query(i, j, 2 * node + 1, (b + e) / 2 + 1, arrayLen - 1 - e);
if (left == -1)
return tree[node] = right;
if (right == -1)
return tree[node] = left;
if (array[left] <= array[right])
return tree[node] = left;
return tree[node] = right;
}
};
int main() {
int A[10] = { 2, 4, 3, 1, 6, 7, 8, 9, 1, 7 };
segTree t(A, 10);
cout << "getMin(0, 4) = " << t.query(0, 4) << endl;
t.update(1, 0);
cout << "getMin(0, 4) = " << t.query(0, 4) << endl;
t.update(0, -1);
cout << "getMin(0, 4) = " << t.query(0, 4) << endl;
return 0;
}
gsourcecode.wordpress.com 