Witam, niedawno nauczyłem się algorytmu znajdowania max w przedziale [a, b]. Wykorzystuję do tego drzewo przedziałowe, gdyż jest to najbardziej optymalny sposób obliczania max w sytuacji, w której wartości liści drzewa mogą być podmieniane. Niestety nie widzę optymalnego sposobu na znalezienie (w jakimś rozsądnym czasie) indeksu największego elementu. Mógłby ktoś pomóc z algorytmem? Dzięki z góry! :D
Tutaj zamieszczam mój algorytm na znalezienie max w przedziale [a, b]:
int maxNaPrz(int a, int b) {
int l = q + a, p = q + b, maxPr = 0;
//q jest pomocniczą zmienną wynoszącą 2^19 - 1
while (l <= p) {
maxPr = max(maxPr, max(arr[l], arr[p]));
l = (l + 1) >> 1; // inaczej: l = (l + 1) / 2;
p = (p - 1) >> 1; // analogicznie dla p
}
return maxPr;
}