General: Addendum (Pierwiastki)

Public message

- Drzewo pierwiastkowe (o wysokości O(log log n)). Można np. dopisać aktualizacje w pierwiastku, i coś podobnego do aktualizacji na przedziale. Opisane jest tutaj: https://cp-algorithms.com/data_structures/sqrt-tree.html - Mergesort Tree to drzewo przedziałowe, które w każdym wierzchołku przechowuje posortowany ciąg z tego poddrzewa. Możemy je wykorzystać w „dynamicznych” inwersjach, ale wtedy musimy wykorzystać też specjalną strukturę zbioru. Jest to przykład sytuacji, gdy za pomocą pierwiastków dostajemy elementarne rozwiązanie z małą stałą, choć gorszą złożonością - O(n sqrt(n) log(n)) zamiast O(n log^2(n)). Dorzuciłem wam zadanko implementacyjne (do Pierwszej Krucjaty) na parsowanie (parsing), warto zapoznać się z tematem, bo jest to całkiem przyjemne :) Będą jeszcze zadania z Pierwiastków, ale muszę zdobyć paczki. Na razie macie dwie gwiazdki (Bajkę o dzielnikach i Kontenery), Pawiana i „Dynamiczne inwersje” do zaklepania (warto tutaj użyć STLa – lower_bound, upper_bound, find – żeby uprościć implementację).