Najmniejsza wartość z zakresu

Question

Hejka potrzebuję pomocy z napisaniem takiego programu, ma on zwrócić wartość najmniejszą z podanego zakresu (na wejściu dostaje tablicę z liczbami całkowitym dodatnimi oraz zakresy). Na początku rozwiązałam to w ten sposób, za każdym razem gdy dostawałam nowy zakres szukałam w nim najmniejszej wartości. Jednak przy dużych liczbach przestaje być to optymalne :/ chciałabym to zrobić szybciej. Kolejny mój pomysł to wypełnienie tablicy/wektora I W niej zapisywać najmniejszą wartoś z danego zakresu. Potem wystarczyłoby wyświetlić. Ale nie wiem czy przyśpieszyłoby to znacznie algorytm.

Co myślicie? Macie jakieś pomysły? Będę bardzo wdzięczna za każdą pomoc❤

Dodaje jeszcze kod 

#include<bits/stdc++.h>
using namespace std;
int n,q,a,b; //ilosc liczb w zakresie, liczba zapytan, a b zakres
vector<int> v;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie();
    cout.tie();
    cin>>n>>q; 

    for(int i=0; i<n; i++){
        cin>>a;
        v.push_back(a);
    }
    int najm;
    for(int i=0; i<q; i++){
        cin>>a>>b;
        a--, b--;  //zmniejszam o jeden ze wzgledu na to ze a i b minimalnie moga byc                     jedynka 
                     // wiec dla a==1 chodzi liczbe ktora jest na pozycji 0 
        najm=v[a];
        a++;
        while(a<=b){
            if(v[a]<najm) najm=v[a];
                a++;
        }
        cout<<najm<<endl;
    }
 
 
}

 

Answer 1

Poszukałem chwilę i znalazłem algorytm rozwiązujący ten problem.

Algorytm RMQ - Range Minimum Query

http://io.8lo.pl/articles/rmq_1_1.htm