Witam. Słyszałem gdzieś, że podobno część problemów algorytmicznych można redukować ze złożoności O(n^2) do o(n * sqrt(n)). O ile dobrze pamiętam jeżeli mamy dany jakiś ciąg liczb i mamy do wyboru 2 operacje: zmiana jakiejś liczby na inną albo odczytanie wartości na przedziale, jest ileś zapytań. Najprostszy sposób to sumy prefiksowe i uaktualnienie ich po każdej zmianie. I to zadanie można zrobić z użycie drzewa przedziałowego (logarytmicznie) a podobno także pierwiastkowo. Jak dokładnie, nie mam pojęcia. Mógłby ktoś zweryfikować tą metodę, a właściwie mi ją wytłumaczyć i najlepiej podać jeszcze jakiś klasyczny przykład wykorzystania? Podobno na olimpiadzie czasem można coś z tego zrobić.
Szczerze, to trudno zrozumieć o co Ci dokładnie chodzi. Podejrzewam, że o coś jak Range Minimum Query.
Szukaj hasła Square Root Decomposition.
Na przykładzie zadania "Kontenery", z drugiego etapu tegorocznej OI:
Treść zadania: https://sio2.mimuw.edu.pl/c/oi24-2/p/kon/
I teraz można zauważyć, że jeśli l_i > sqrt(n)
, to można wykonać naiwne stawianie, zwiększenie wartości w tablicy co l_i
ty element, gdyż takich operacji będzie maksymalnie sqrt(n)
. Jeśli jednak l_i
jest większe od pierwiastka, to można trzymać w jednej tablicy długości d_i
ile "przedziałów" jest otwartych (z początkami modulo d_i
) i podczas wypisywania jedynie patrzeć ile z tych przedziałów było otwartych (oczywiście, trzeba trzymać wartości modulo d_i
, bo to mówi czy ustawiono kontener czy nie). Takich różnych reszt jest maksymalnie sqrt(n)
, gdyż mamy warunek, że d_i * l_i <= n
, a skoro l_i > sqrt(n)
, to d_i < sqrt(n)
. Sumarycznie, w obu przypadkach daje to złorzoność O(n sqrt(n))
. Jeśli coś niejasne, pytaj.