Próbuję zrobićlina struktura danych. Jest to rodzaj drzewa binarnego, tj. Rekurencyjna struktura danych.

Celem liny jest to, aby podział i konkatenacja byłyszybki, co znaczyunikniesz kopiowania całych lin.
Na przykład użytkownik powinien móc powiedziećrope1 + rope2 i oczekuj wyniku w czasie ~ logarytmicznym.

To jednak stanowi problem:
Jeśli lina zostanie zmodyfikowana, jej rodzice również zostaną zmodyfikowani pośrednio.
Ponieważ moim celem jest zrobienierope wymiana zastępcza nastring, To nie jest do zaakceptowania.

Moje rozwiązanie to: zawsze, gdy jestkażdy rodzaj zmiany na arope, StworzyłbymNowy węzeł, z niewielką zmianą, pozostawiając stare niezmodyfikowane.

Teoretycznie myślę, że to działa dobrze.

W praktyce wymaga to jednak alokacji stertyza (prawie?) każdą modyfikację sznurków.
Nawet zmiana jednoznakowa spowodowałaby powstanie nowego obiektu sterty, który jest nie tylko powolny sam w sobie, ale także znacznie zmniejsza lokalność pamięci, co bardzo negatywnie wpływa na wydajność.

Jak mam rozwiązać ten problem?