[BotRekrutacyjny]

Proszę o jakiś tutorial do drzew przedziałowych, najlepiej żeby była wytłumaczona implementacja.

#programowanie #algorytmy #cpp

[cevilo]

@BotRekrutacyjny: algorytmy + struktury danych = programy

[ZdeformowanyKreciRyj]

@BotRekrutacyjny: link
nic lepszego po polsku raczej nie znajdziesz. Tu bez implementacji ale punkt przedział jest banalne do zaklepania jak zrozumiesz jak działa.

[BotRekrutacyjny]

@ZdeformowanyKreciRyj: samą ideę powiedzmy, że rozumiem, mam jakieś dane i muszę skrócić wyszukiwanie minimum i maksimum na danym przedziale, a nie mam pojęcia jak się do tego zabrać, jak utworzyć te drzewo, czy to powinny być wskaźniki, czy może tablica

[ZdeformowanyKreciRyj]

@BotRekrutacyjny: zależy od zadania bo można tworzyć dynamiczne drzewa przedziałowe co nawet masz chyba opisane w tym moim linku, ale w większości przypadków wystarczy Ci tablica stałego rozmiaru jeżeli znasz z góry wielkość całego przedziału

[BotRekrutacyjny]

@ZdeformowanyKreciRyj: w momencie kompilacji nie znam długości ciągu liczb, dzięki za linka, mam nadzieję, że mi trochę rozjaśni

[ZdeformowanyKreciRyj]

@BotRekrutacyjny: nie musisz znać długości ciągu liczb w momencie kompilacji. Wystarczy, że znasz tą długość zanim zaczniesz odpowiadać na pytania o min/max na przedziale. Jak coś to priv

[Z.....e]

Tu masz kilka linków:

www.geeksforgeeks.org/segment-tree-efficient-implementation/amp/

https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/amp/

https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/amp/

Ogolnie polecam tę stronę, jest na niej dosłownie wszystko i w dodatku dosyć dobrze wytłumaczone i w przystępny sposób