Problem

Powrót do listy wątków

Jak zaprząc drzewo przedziałowe (bądź coś innego) do takiego problemu :

Mamy ciąg n dodatnich liczb całkowitych. Chcemy określić, ile jest liczb mniejszych od zadanej liczby "a" na zadanym przedziale [pocz,kon]. Paweł Maśluch, 2015-06-25 00:23:41
Można w każdym węźle drzewa przedziałowego trzymać wszystkie elementy z odpowiedniego przedziału - w jakimś secie. Wtedy, po rozbiciu na przedziały bazowe dla każdego przedziału liczy się liczbę elementów <= a na tym przedziale (binary search po secie).

To jest nlog^2n - może da się szybciej. Tomasz Ponitka, 2015-06-25 23:14:37
Rozumiem, że to rozwiązanie będzie działało, gdy dorzucimy operację zamiany 2 elementów ciągu (według mnie, dopóki ścieżki wychodzące z tych 2 elementów się nie spotkały, to w określonym węźle usuwamy 1 element, a wstawiamy drugi) ?

To rozwiązanie będzie wymagało stosunkowo dużej pamięci ( rzędu O( n * log n ) ) ? Paweł Maśluch, 2015-06-28 12:24:34
Jest jeszcze jeden szkopuł : jak w secie zliczać elementy mniejsze od zadanego ? Paweł Maśluch, 2015-06-28 12:40:09
Zamiana wartości elementu: na ścieżce od odpowiedniego węzła do korzenia usunąć w setach poprzednią wartość, dodać nową.

Pamięć: O(n log n)

Zliczanie el. < a w secie wygląda mniej więcej tak: distance(S.begin(), S.lower_bound(a)); (http://www.cplusplus.com/reference/set/set/lower_bound/, http://www.cplusplus.com/reference/iterator/distance/)
Tomasz Ponitka, 2015-06-28 13:33:46
Niestety:
z dokumentacji funkcji distance, którą dołączyłeś:
"If it is a random-access iterator, the function uses operator- to calculate this. Otherwise, the function uses the increase operator (operator++) repeatedly." Karol Pokorski, 2015-07-01 15:21:19
Można natomiast w węźle drzewa trzymać dynamicznie rozwijalne drzewo przedziałowe sumujące ile jest zadanych elementów. Karol Pokorski, 2015-07-01 15:22:44