Pobieranie maksymalnej wartości z zakresu w nieposortowanej tablicy

Mam nieposortowaną tablicę . Mam zapytania, w których podaję zakres, a następnie zwracana jest maksymalna wartość z tego zakresu. Na przykład:

array[]={23,17,9,45,78,2,4,6,90,1};
query(both inclusive): 2 6
answer: 78

Jaki algorytm lub strukturę danych tworzę, aby szybko uzyskać maksymalną wartość z dowolnego zakresu. (Istnieje wiele zapytań)

EDYCJA: To jest rzeczywiście prosta wersja rzeczywistego problemu. Mogę mieć rozmiar tablicy nawet 100000, a liczbę zapytań do 100000. Zdecydowanie wymagam wcześniejszego przetworzenia, które ułatwi szybką odpowiedź na zapytanie.

Myślę, że możesz zbudować jakieś drzewo binarne, w którym każdy węzeł reprezentuje maksymalną wartość jego dzieci:

            78           
     45            78     
  23    45     78      6  
23 17  9 45   78 2    4 6   

Następnie musisz tylko znaleźć sposób, aby określić, które węzły minimalnie musisz sprawdzić, aby znaleźć maksymalną wartość w pytanym zakresie. W tym przykładzie, aby uzyskać maksymalną wartość z zakresu indeksu [2, 6](włącznie), max(45, 78, 4)zamiast tego max(9, 45, 78, 2, 4). W miarę wzrostu drzewa zysk będzie większy.

Uzupełnienie odpowiedzi ngoaho91.

Najlepszym sposobem rozwiązania tego problemu jest użycie struktury danych drzewa segmentów. To pozwala ci odpowiadać na takie zapytania w O (log (n)), co oznaczałoby, że całkowita złożoność twojego algorytmu wynosiłaby O (Q logn), gdzie Q jest liczbą zapytań. Jeśli użyjesz naiwnego algorytmu, całkowita złożoność wyniesie O (Q n), co jest oczywiście wolniejsze.

Wadą drzew segmentowych jest jednak wada. Zajmuje dużo pamięci, ale często mniej zależy ci na pamięci niż na szybkości.

Pokrótce opiszę algorytmy używane przez ten DS:

Drzewo segmentów jest tylko specjalnym przypadkiem drzewa wyszukiwania binarnego, w którym każdy węzeł przechowuje wartość zakresu, do którego jest przypisany. Węzłu root przypisano zakres [0, n]. Lewemu dziecku przypisano zakres [0, (0 + n) / 2], a prawemu dziecku [(0 + n) / 2 + 1, n]. W ten sposób drzewo zostanie zbudowane.

Utwórz drzewo :

/*
    A[] -> array of original values
    tree[] -> Segment Tree Data Structure.
    node -> the node we are actually in: remember left child is 2*node, right child is 2*node+1
    a, b -> The limits of the actual array. This is used because we are dealing
                with a recursive function.
*/

int tree[SIZE];

void build_tree(vector<int> A, int node, int a, int b) {
    if (a == b) { // We get to a simple element
        tree[node] = A[a]; // This node stores the only value
    }
    else {
        int leftChild, rightChild, middle;
        leftChild = 2*node;
        rightChild = 2*node+1; // Or leftChild+1
        middle = (a+b) / 2;
        build_tree(A, leftChild, a, middle); // Recursively build the tree in the left child
        build_tree(A, rightChild, middle+1, b); // Recursively build the tree in the right child

        tree[node] = max(tree[leftChild], tree[rightChild]); // The Value of the actual node, 
                                                            //is the max of both of the children.
    }
}

Drzewo zapytań

int query(int node, int a, int b, int p, int q) {
    if (b < p || a > q) // The actual range is outside this range
        return -INF; // Return a negative big number. Can you figure out why?
    else if (p >= a && b >= q) // Query inside the range
        return tree[node];
    int l, r, m;
    l = 2*node;
    r = l+1;
    m = (a+b) / 2;
    return max(query(l, a, m, p, q), query(r, m+1, b, p, q)); // Return the max of querying both children.
}

Jeśli potrzebujesz dodatkowych wyjaśnień, daj mi znać.

BTW, Drzewo segmentów obsługuje także aktualizację pojedynczego elementu lub zakresu elementów w O (log n)

Najlepszy algorytm byłby w czasie O (n), ponieważ poniżej zacznijmy od końca, indeks granic zakresu

int findMax(int[] a, start, end) {
   max = Integer.MIN; // initialize to minimum Integer

   for(int i=start; i <= end; i++) 
      if ( a[i] > max )
         max = a[i];

   return max; 
}

Rozwiązania oparte na drzewku binarnym / drzewie segmentu rzeczywiście wskazują właściwy kierunek. Można jednak sprzeciwić się, że wymagają one dużo dodatkowej pamięci. Istnieją dwa rozwiązania tych problemów:

1. Użyj niejawnej struktury danych zamiast drzewa binarnego
2. Użyj drzewa M-ary zamiast drzewa binarnego

Pierwszą kwestią jest to, że ponieważ drzewo ma wysoką strukturę, możesz użyć struktury podobnej do sterty, aby domyślnie zdefiniować drzewo, zamiast reprezentować drzewo za pomocą węzłów, lewego i prawego wskaźnika, interwału itp. To oszczędza dużo pamięci, zasadniczo brak wydajności - musisz wykonać trochę więcej arytmetyki wskaźnika.

Druga kwestia polega na tym, że kosztem nieco więcej pracy podczas oceny można użyć drzewa M-ary zamiast drzewa binarnego. Na przykład, jeśli używasz drzewa 3-arylowego, obliczysz maksymalnie 3 elementy jednocześnie, następnie 9 elementów jednocześnie, a następnie 27 itd. Wymagane dodatkowe miejsce to N / (M-1) - możesz udowodnij, używając formuły serii geometrycznej. Na przykład, jeśli wybierzesz M = 11, będziesz potrzebować 1/10 miejsca na metodę drzewa binarnego.

Możesz sprawdzić, czy te naiwne i zoptymalizowane implementacje w Pythonie dają te same wyniki:

class RangeQuerier(object):
    #The naive way
    def __init__(self):
        pass

    def set_array(self,arr):
        #Set, and preprocess
        self.arr = arr

    def query(self,l,r):
        try:
            return max(self.arr[l:r])
        except ValueError:
            return None

vs.

class RangeQuerierMultiLevel(object):
    def __init__(self):
        self.arrs = []
        self.sub_factor = 3
        self.len_ = 0

    def set_array(self,arr):
        #Set, and preprocess
        tgt = arr
        self.len_ = len(tgt)
        self.arrs.append(arr)
        while len(tgt) > 1:
            tgt = self.maxify_one_array(tgt)
            self.arrs.append(tgt)

    def maxify_one_array(self,arr):
        sub_arr = []
        themax = float('-inf')
        for i,el in enumerate(arr):
            themax = max(el,themax)
            if i % self.sub_factor == self.sub_factor - 1:
                sub_arr.append(themax)
                themax = float('-inf')
        return sub_arr

    def query(self,l,r,level=None):
        if level is None:
            level = len(self.arrs)-1

        if r <= l:
            return None

        int_size = self.sub_factor ** level 

        lhs,mid,rhs = (float('-inf'),float('-inf'),float('-inf'))

        #Check if there's an imperfect match on the left hand side
        if l % int_size != 0:
            lnew = int(ceil(l/float(int_size)))*int_size
            lhs = self.query(l,min(lnew,r),level-1)
            l = lnew
        #Check if there's an imperfect match on the right hand side
        if r % int_size != 0:
            rnew = int(floor(r/float(int_size)))*int_size
            rhs = self.query(max(rnew,l),r,level-1)
            r = rnew

        if r > l:
            #Handle the middle elements
            mid = max(self.arrs[level][l/int_size:r/int_size])
        return max(max(lhs,mid),rhs)

wypróbuj strukturę danych „segment tree”
istnieją 2 kroki
build_tree () O (n)
zapytanie (int min, int max) O (nlogn)

http://en.wikipedia.org/wiki/Segment_tree

edytować:

po prostu nie czytacie wiki, którą wysłałem!

algorytm ten:
- przemierzasz tablicę 1 raz, aby zbudować drzewo. O (n)
- kolejne 100000000+ razy, kiedy chcesz poznać maksimum dowolnej części tablicy, po prostu wywołaj funkcję zapytania. O (logowanie) dla każdego zapytania
- c ++ zaimplementuj tutaj geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
stary algorytm to:
każde zapytanie, wystarczy przejść przez zaznaczony obszar i znaleźć.

więc jeśli użyjesz tego algorytmu do przetworzenia raz, OK, będzie wolniejszy niż stary sposób. ale jeśli będziemy przetwarzać ogromną liczbę zapytań (w mld), to bardzo wydajny można wygenerować plik tekstowy takiego, dla testowanej

linii 1: 50000 liczba losowa z 0-1000000, podzielone przez „(spacja)” (jest to tablica)
linia 2: 2 losowa liczba od 1 do 50000, podzielona przez „(spację)” (to zapytanie)
...
linia 200000: lubi linię 2, to również losowe zapytanie

jest to przykładowy problem, przepraszam, ale jest to w języku wietnamskim
http://vn.spoj.com/problems/NKLINEUP/,
jeśli rozwiążesz go starym sposobem, nigdy nie przejdziesz.

Możesz osiągnąć O (1) na zapytanie (z konstrukcją O (n log n)) za pomocą struktury danych zwanej tabelą rzadką. Dla każdej potęgi 2 zachowajmy maksimum dla każdego odcinka tej długości. Teraz dany segment [l, r) daje maksimum maksimum dla [l + 2 ^ k) i [r-2 ^ k, r) dla odpowiedniego k. Nakładają się na siebie, ale jest OK