Минимум на неизменяемом отрезке O (N²+K)

Дан массив из N целых чисел и K запросов, состоящих из двух индексов.
Необходимо для каждого запроса вывести минимальный из элементов, расположенных между индексами в запросе.

    Воспользуемся динамическим программированием. Пусть M[i][d] = минимальный из элементов массива с индексами от i до i + d включительно, тогда, очевидно, что M[i][0] = a[i] и M[i][d] = min (a[i + d], M[i][d - 1]).
    Минимальное из чисел от i до j будет равно M[i][j - i].

Асимптотика O(N²+K).

Листинг C++

class table_min
{
private :
    int n;
    vector < int > a;
    vector < vector < int > > M;

public :
    table_min (vector < int > v)
    {
        int i, j;
        a = v;
        n = v.size ();

        M.assign (n, vector < int > (n, (int)2e9));
        for (i = 0; i < n; ++ i)
            M[i][0] = a[i];

        for (j = 1; j < n; ++ j)
            for (i = 0; i + j < n; ++ i)
                M[i][j] = :: min (M[i][j - 1], a[i + j]);
    }

    int min (int l, int r)
    {
        return M[l][r - l];
    }
};

19:00
04.08.2009

По всем вопросам обращаться: rumterg@gmail.com

Минимум на неизменяемом отрезке O (N2+K)

Минимум на неизменяемом отрезке O (N²+K)