Moze hint?
z-slaganje
Koristi podintervalna stabla (ili kako se vec zovu :))
Sa naglaskom na stabla. Razmisli kako bi cuvao podatke u stablu, tako da mozes "brzo" da dodjes do informacija ko se traze.
Ja bi ti preporucio da sam probas da svatis sta bi, i kako cuvao u stablu, a ne da google-ujes, i trazis ta stabla.
Poz,
Z-Admin
Ja bi ti preporucio da sam probas da svatis sta bi, i kako cuvao u stablu, a ne da google-ujes, i trazis ta stabla.
Poz,
Z-Admin
Znaci vrijeme je da i to iskodiram...
Upoznat sam s intervalnim stablom, ali nisam nikad radio s njim.
Hvala.
Upoznat sam s intervalnim stablom, ali nisam nikad radio s njim.
Hvala.
Moze li neko da ispise detaljnije objasnjenje za rjesavanje ovog zadatka?
Pa jesi li probao ishta sa nekim stablima, recimo intervalnim?
Ne znam ta intervalna stabla. Posto vam je verovatno mrsko kuckati ovde, moze li makar neki eksterni link gde mogu malo vise procitati o svemu tome?
Mada, najbolje bi bilo da se srpski ovde to malo pojasni... Ako neko ima zivaca...
Mada, najbolje bi bilo da se srpski ovde to malo pojasni... Ako neko ima zivaca...
Pa to ti je vrsta binarnog stabla koja ima 2^n listova. Kao i heap, realizuje se preko niza, bar je tako lakse :)
Recimo da imas niz od 8 brojeva i imas binarno stablo
To su ti ujedno i indexi u nizu koji predstavlja segmentno stablo. Svaki otac ima sinove 2 * i, 2 * i + 1. E sad, recimo da te zanima suma celog niza. Prosto ces pitati sumu indexa 1. Znaci, otac je odgovoran za sve svoje sinove. Ako te zanima suma elemenata od 4-8. Otac ti je odgovoran za elemente od 1-8 pa moras da pitas sinove. Pa onda upit podelis na 4-4 (to je posao levog sina) i 5-8 (to je posao desnog sina). Levi sin je odgovoran za interval 1-4 (to je onaj u stablu sa indexom 2), a desni sin za 5-8. Desni sin ti odgovara i njegovu vrednost uzimas. Dalje razvijas levog sina. On pita svog levog sina (index 4) koji je odgovoran za 1-2, ali to mu ne treba je mu treba interval 4-4. Pita desnog sina koji je odgovoran za 3-4. Desni sin takodje pita levog i desnog, ali desni mu treba jer je desni odgovoran za 4-4 (index 11) i to je ujedno i list i tu prestaje pretraga. To ti je bio upt za neku vrednost.
Kad radis update, ondosno ako ubacujes vrednost za neki list (recimo da si izmenio vrednost nekog elementa niza) onda ide isto to, samo se vracas od lista prema korenu :)
Znaci, ako je otac odgovoran za interval 2^i - 2^j, onda je levi sin odgovoran za 2^i - (2^j + 2^i) / 2, a desni za ((2^j + 2^i) / 2 + 1) - 2^j
Eto, nije sigurno najjasnije, ali ti pitaj itd, probaj nesto na netu pa ce se nastaviti...
Recimo da imas niz od 8 brojeva i imas binarno stablo
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
To su ti ujedno i indexi u nizu koji predstavlja segmentno stablo. Svaki otac ima sinove 2 * i, 2 * i + 1. E sad, recimo da te zanima suma celog niza. Prosto ces pitati sumu indexa 1. Znaci, otac je odgovoran za sve svoje sinove. Ako te zanima suma elemenata od 4-8. Otac ti je odgovoran za elemente od 1-8 pa moras da pitas sinove. Pa onda upit podelis na 4-4 (to je posao levog sina) i 5-8 (to je posao desnog sina). Levi sin je odgovoran za interval 1-4 (to je onaj u stablu sa indexom 2), a desni sin za 5-8. Desni sin ti odgovara i njegovu vrednost uzimas. Dalje razvijas levog sina. On pita svog levog sina (index 4) koji je odgovoran za 1-2, ali to mu ne treba je mu treba interval 4-4. Pita desnog sina koji je odgovoran za 3-4. Desni sin takodje pita levog i desnog, ali desni mu treba jer je desni odgovoran za 4-4 (index 11) i to je ujedno i list i tu prestaje pretraga. To ti je bio upt za neku vrednost.
Kad radis update, ondosno ako ubacujes vrednost za neki list (recimo da si izmenio vrednost nekog elementa niza) onda ide isto to, samo se vracas od lista prema korenu :)
Znaci, ako je otac odgovoran za interval 2^i - 2^j, onda je levi sin odgovoran za 2^i - (2^j + 2^i) / 2, a desni za ((2^j + 2^i) / 2 + 1) - 2^j
Eto, nije sigurno najjasnije, ali ti pitaj itd, probaj nesto na netu pa ce se nastaviti...