Find minimum element of a subsequence

Question

Given a sequence S of n integer elements, I need a function min(i,j) that finds the minimum element of the sequence between index i and index j (both inclusive) such that:

1. Initialization takes O(n);
2. Memory space O(n);
3. min(i,j) takes O(log(n)).

Please suggest an algorithm for this.

Answer 1

Segmenttree is that what you need because it fulfils all your requirements.

1. Initialisation takes O(n) with Segment Tree
2. Memory is also O(n)
3. Queries can be done in O(log n)

Beside this, the tree is dynamic and can support updating in O(log n). This means one can modify the element of some element i in O(log n) and still retrieve the minimum.