Algorytmiczne zastosowania trwałych struktur danych

Używamy trwałych struktur danych aby zastosować technikę zamiatania z geometrii obliczeniowej do rozwiązywania pewnej klasy problemów dotyczących zapytań na tablicach i drzewach. Wykorzystujemy to podejście żeby stworzyć optymalne lub prawie optymalne, nieskomplikowane rozwiązania różnych problemów, zarówno wcześniej badanych jak i nowych. Dodatkowo, pokazujemy jak można zastosować trwałe struktury danych do przechowywania ciągów znaków, aby móc je szybko dzielić i łączyć.Implementujemy trwałe zrównoważone drzewo binarne i używamy go do rozwiązania wyżej wspomnianych problemów.

We use persistent data structures to apply sweeping technique from computational geometry to a certain class of query problems on arrays and trees. We employ this approach to develop optimal or near-optimal, conceptually simple solutions to various problems, both previously studied and new. Additionally, we show how persistent data structures can be used for storing strings to allow fast split and concatenate operations.We develop a generic implementation of persistent self-balancing binary tree, which we use to solve the aforementioned problems.