Informatyczny kącik olimpijski

Problem (MAX, +) kontratakuje

Tym razem wyjątkowo nie omówimy żadnego nowego zadania. Wrócimy za to do problemu przedstawionego w $Δ4 13$ w artykule Złośliwy problem $|(MAX ;+)$ i kubełkowe struktury danych...

Problem ten wygląda następująco: Dany jest ciąg złożony z $|n$ liczb całkowitych $c1,c2,...,cn.$ Na tym ciągu chcemy wykonywać dwa typy operacji: (1) przypisanie wartości $k$ każdemu elementowi ciągu o indeksie z przedziału $|[i.. j]$ i wartości mniejszej niż $|k$ (operacja $update(i, j,k)$ ) oraz (2) zapytanie o sumę elementów ciągu o indeksach z przedziału $[i.. j]$ (operacja $|quary(i, j)$ ).

W oryginalnym artykule przedstawiona była struktura danych, która $m$ takich operacji potrafi wykonać w czasie $|𝒪(n + m$ Autor tamtego opracowania (Wojciech Śmietanka) zorganizował wówczas konkurs na poprawę tej złożoności, który udało mi się wtedy wygrać, uzyskując wynik $2 |𝒪(n log n +m$ Niedawno w algorytmicznej społeczności pojawił się jeszcze lepszy pomysł, który przedstawię w dzisiejszym kąciku. Nie dość, że rozwiązuje on nasz problem w czasie $𝒪((n + m)$ to jeszcze korzysta wyłącznie ze zwykłego drzewa przedziałowego! (Choć to, jakie konkretnie informacje będziemy przechowywać w każdym przedziale bazowym, jest - według mnie - dość nieintuicyjne.)

Przejdźmy do sedna. W każdym wierzchołku drzewa przedziałowego będziemy utrzymywać następujące informacje o elementach zawartych w jego przedziale bazowym: $min$ - minimalna wartość wśród elementów z przedziału; $count -min$ - liczba elementów o wartości równej $min$ ; $|second -min$ - najmniejsza wartość elementu różna od $min$ lub nieskończoność, jeśli wszystkie wartości w przedziale są równe; $|sum$ - suma wartości elementów; $lazy$ - wartość $k,$ o jaką należy zaktualizować dzieci przedziału bazowego, aby wartości w nich przechowywane stały się aktualne, lub null, gdy wartości w dzieciach są aktualne.

Po pierwsze, zachęcamy Czytelnika do przekonania się, że z aktualnych wartości dla dzieci przedziału bazowego możemy odzyskać wartości dla ojca. Następnie razem przeanalizujmy, w jaki sposób aktualizujemy konkretny przedział bazowy o nową wartość $|k.$ Jeśli $|k⩽ min,$ to nie robimy nic. Nawet najmniejsza wartość nie zostanie zmieniona na $|k.$ Jeśli $min < k < second-min,$ to wszystkie elementy o wartości $|min$ zamienią się na elementy o wartości $k,$ czyli przypisujemy $|min = k$ oraz $sum = sum + count-min ⋅(k − min).$ Przypisujemy również $|lazy = k,$ być może nadpisując mniejszą wartość $lazy.$ Jeśli $|second -min ⩽ k,$ to rekurencyjnie aktualizujemy dzieci przedziału bazowego i w czasie stałym odzyskujemy z nich informacje o ojcu.

Otrzymując zapytanie o przedział $[i.. j],$ rekurencyjnie rozkładamy go na przedziały bazowe. Jeśli w rekurencji natrafimy na przedział z wartością $|lazy ≠ null,$ to - jak wyżej - aktualizujemy jego dzieci. Następnie można odzyskać sumę albo zaktualizować owe przedziały bazowe i odzyskać wartości ich przodków w drzewie.

Sama poprawność algorytmu jest dość oczywista. Jednak skąd bierze się tak dobra złożoność czasowa? Nietrudno skonstruować przykład, w którym jedna operacja $update(i, j,k)$ zajmie czas $𝒪(n).$ Problemem są zejścia rekurencyjne, gdy $second -min ⩽ k.$ Oznaczmy ich liczbę przez $x.$ Poza nimi wszystko działa jak w zwykłych drzewach przedziałowych, więc nasz algorytm działa w czasie $𝒪(x + n + m$

Przejdźmy do dokładniejszej analizy algorytmu. Weźmy przedział bazowy $|P.$ Jeśli w jakimś nadprzedziale przypisaliśmy wartość $lazy = k,$ to w nim całym była tylko jedna wartość nie większa niż $k,$ w szczególności $|k$ było mniejsze niż $second min$ dla $P.$ Dowodzi to, iż wartości $|second -min$ zawsze pozostają aktualne. Z tego powodu przy propagowaniu wartości $lazy$ nie natrafimy na przypadek $second -min ⩽ k.$ Całe $|x$ pochodzi więc z aktualizacji przedziałów bazowych o nowe wartości $|k.$

Aby oszacować wartość $x$ w terminach $|n$ oraz $|m,$ wprowadzimy pojęcie potencjału. Dla danego przedziału bazowego możemy policzyć, ile jest w nim różnych wartości. Potencjałem dla ciągu nazwijmy sumę tych wartości, liczoną po wszystkich przedziałach bazowych. Potencjał ten będzie największy, jeśli wszystkie wartości w ciągu będą różne. Będzie on wtedy wynosił tyle, ile suma długości przedziałów bazowych, czyli $|𝒪(n log n).$

Najpierw zastanówmy się, kiedy nasz potencjał może się zwiększyć za względu na dany przedział bazowy $|P.$ Przy operacji $|update(i, j,k)$ zbiór wartości w $P$ może się powiększyć co najwyżej o jeden element - o element o wartości $k.$ Aby tak się stało, musi zachodzić $k > min,$ w przeciwnym razie żaden element w $P$ nie otrzyma nowej wartości $|k.$ Ponadto przedział $|[i.. j]$ nie może zawierać całego $|P,$ w przeciwnym razie usuniemy wartość $|min$ ze zbioru wartości z $P$ i potencjał się nie zwiększy. Liczba przedziałów bazowych, które przecinają się z $|[i.. j],$ a nie są zawarte w $[i.. j],$ wynosi $𝒪(log n),$ a są to dokładnie te przedziały, które odwiedzamy rekurencyjnie, rozkładając $[i.. j]$ na przedziały bazowe. Ze względu na każdy z tych $𝒪(log n)$ przedziałów potencjał zwiększy się o co najwyżej jeden.

Nasz potencjał na początku wynosił co najwyżej $𝒪(n log n),$ a podczas każdej z $m$ operacji wzrośnie o co najwyżej $𝒪(log n),$ a więc może też zmaleć co najwyżej $𝒪(n log n)+ m$ razy.

Wróćmy do naszego problematycznego przypadku, czyli gdy w aktualizowanym o wartość $k$ przedziale zachodzi $second min ⩽ k.$ Wszystkie elementy o wartościach $|min$ oraz $second -min$ będę po aktualizacji miały wartość równą $k,$ czyli liczba różnych wartości w aktualizowanym przedziale bazowym zmaleje i zmaleje też potencjał. W ten sposób ograniczyliśmy $|x$ przez $|𝒪((n + m)$ a cały algorytm, tak jak postulowaliśmy, zadziała w czasie $𝒪((n + m)$