Find minimum in i-j range less than in O(j-i) using less than O(N^2) memory

Question

Say there is a big array that containes N integers:

const unsigned N = 1e12;
int array[N] = { 1, 3 , 8, -5, 4, 3, -1 -6, 6, ....., N};

There should be queried many times the smallest element in the range of different i j indecies. THe complexity of returning the minimum should be smaller than in O(j-i) and the problem should be solved using less than O(N^2) memory.

How this can be done?

Answer 1

For static array, as you mentioned, the fastest solution is O(1) with O(n) preproc. But in practice you may want to use one of the following approaches, which also work for dynamic arrays, and seem to me easier to understand and code:

1. divide the array into sqrt(n) sections, each with sqrt(n) elements, and store minimums for each of those segments. Each (i,j) will contain some of those segments entirely plus maybe some elements from left and right. Pass over these elements and stored answers for segments to find the min. This requires O(n) preproc, O(sqrt(n)) query, O(sqrt(n)) update and O(sqrt(n)) memory. Also very easy to code.
   
2. build a minumum segment tree over the array. This gives O(logn) for query/update, O(n) memory/preproc.