Korzystanie binarnych indeksowane drzew o przedłużenie RMQ

Question

RMQ problem można rozszerzyć tak:

Zważywszy jest tablicą n całkowitymi A.

zapytania (x, y) podane dwie liczby całkowite 1 ≤ x, y ≤ n znajdź najmniej A[x], A[x+1], ... A[y];

aktualizacji (x, t) podano liczbę całkowitą v i 1 ≤ x ≤ n do A[x] = v. Ten problem można rozwiązać w O(log n) dla obu operacji przy użyciu segment trees.

Jest to wydajne rozwiązanie na papierze, ale w praktyce drzewa segmentowe wiążą się z dużym obciążeniem, zwłaszcza jeśli są implementowane rekursywnie.

Wiem na pewno, że istnieje sposób rozwiązania problemu w O(log^2 n) dla jednego (lub obu, nie jestem pewien) operacji, przy użyciu drzew indeksowanych binarnie (można znaleźć więcej zasobów, ale this i this są, IMO, najbardziej zwięzłe i wyczerpujące, odpowiednio). To rozwiązanie dla wartości n, które pasują do pamięci, jest w praktyce szybsze, ponieważ BIT mają dużo mniej narzutów.

Jednak nie wiem, w jaki sposób struktura BIT jest używana do wykonywania danych operacji. Wiem tylko, jak go użyć do wysłania zapytania na przykład na sumę interwałową. Jak mogę go użyć, aby znaleźć minimum?

Jeśli to pomaga, mam kod napisany przez innych, który robi to, o co proszę, ale nie mogę zrozumieć tego. Oto taki kawałek kodu:

int que(int l, int r) { 
    int p, q, m = 0; 

    for(p=r-(r&-r); l<=r; r=p, p-=p&-p) { 
     q = (p+1 >= l) ? T[r] : (p=r-1) + 1; 
     if(a[m] < a[q]) 
      m = q; 
    } 

    return m; 
} 

void upd(int x) { 
    int y, z; 
    for(y = x; x <= N; x += x & -x) 
     if(T[x] == y) { 
      z = que(x-(x&-x) + 1, x-1); 
      T[x] = (a[z] > a[x]) ? z : x; 
     } 
     else 
      if(a[ T[x] ] < a[ y ]) 
       T[x] = y; 
} 

W powyższym kodu T inicjowany jest 0, a jest podana tablica, N jego wielkość (robią indeksy od 1 do dowolnego powodu) i upd nazywa się najpierw dla każdej wartości odczytu. Przed upd jest wywoływana a[x] = v jest wykonywana.

Również, p & -p jest taki sam jak p^(p & (p - 1)) w niektórych źródłach BIT i indeksowanie rozpoczyna się od 1 z elementem zerowym zainicjowanym do nieskończoności.

Czy ktoś może wyjaśnić, jak powyższe działa lub jak mogę rozwiązać dany problem z BIT?

Answer 1

Od poziomie powyżej bitowym fiddling, to co mamy:

zwykła tablica BIT g do tablicy danych Integer a sklepach wahają sum.

g[k] = sum{ i = D(k) + 1 .. k } a[i] 

gdzie D(k) tylko k z najniższego rzędu 1 bitu 0. Tutaj mamy zamiast

T[k] = min{ i = D(k) + 1 .. k } a[i] 

Kwerenda działa dokładnie tak jak normalny zakres BIT zapytania suma ze zmianą że minima podzakresów są brane jako zapytanie, a nie sumy. Dla N pozycji w a, istnieją bity sufitu (log N) w N, który określa czas działania.

Aktualizacja wymaga więcej pracy, ponieważ zmiana ma wpływ na minima podzakresów O (log N) - tj. Elementy o numerze g - i każda z nich sama rozpatruje kwerendę O (log N). To sprawia, że ​​aktualizacja O (log^2 n) jest ogólnie.

Na poziomie skrzypienia jest to diabelsko sprytny kod. Oświadczenie x += x & -x usuwa kolejny ciąg kolejnych 1 w x, a następnie ustawia następny najwyższy z rzędu na 1. To jest właśnie to, czego potrzebujesz, aby "przejść" BIT dla oryginalnej liczby całkowitej x.

Answer 2

Drzewka segmentowe są również skutecznym rozwiązaniem w praktyce. Nie stosujesz ich jednak jako drzew. Runda n do następnej potęgi dwóch i użyj tablicy rmq o rozmiarze 2*n. Ostatnie wpisy n z rmq to A. Jeśli j < n, to rmq[j] = min(rmq[2*j], rmq[2*j+1]). Wystarczy spojrzeć logarytmicznie na wiele pozycji o numerze rmq, aby odpowiedzieć na zapytanie o zakresie minimalnym. I musisz tylko zaktualizować logarytmicznie wiele wpisów rmq, gdy wpis A jest zaktualizowany.

Nie rozumiem twojego kodu, więc nie zamierzam tego komentować.

Answer 3

Nie wyglądał na kod w szczegółach, ale wydaje się być mniej więcej zgodne z poniższym schematem:

1) zachować strukturę bitu, czyli nałożenie struktury drzewa na podstawie uprawnień dwóch na tablicy.

2) W każdym węźle drzewa zachować minimalną wartość znalezioną u dowolnego potomka tego węzła.

3) Biorąc pod uwagę dowolny zakres, połóż wskaźniki na początku i końcu zakresu i przesuń je w górę, dopóki się nie spotkają. Jeśli przesuniesz wskaźnik w górę iw kierunku drugiego wskaźnika, właśnie wprowadziłeś węzeł, w którym każdy potomek jest członkiem zakresu, więc zwróć uwagę na tę wartość w tym węźle. Jeśli przesuniesz wskaźnik w górę i od drugiego wskaźnika, węzeł, do którego właśnie dołączyłeś, nagrywa minimum uzyskane z wartości, w tym poza zakresem, i zauważyłeś już każdą odpowiednią wartość poniżej tego węzła w zasięgu, więc zignoruj wartość w tym węźle.

4) Gdy oba wskaźniki są tymi samymi wskaźnikami, minimalna wartość z zakresu jest wartością minimalną w każdym węźle, który został zapamiętany.