|
Titlul: Răspuns: 007 Arbori de intervale Scris de: alexjj din Noiembrie 17, 2004, 19:42:04 Question : Cum modific algoritmul de determinare a sumei dintre doua pozitii a unui vector (care foloseste evident arbori de intervale) ca sa calculez minimul ?. (Mentionez ca nu vreau sa mi sa raspunda cu USE RMQ, e pe info.devnet).
Thank you for reading this ! Titlul: Răspuns: 007 Arbori de intervale Scris de: Cristian Strat din Noiembrie 17, 2004, 22:19:38 Daca ai nevoie de minim intre 1 si X poti folosi foarte usor AIB.
Daca iti trebuie intre i si j trebuie sa modifici foarte putin algoritmul ce determina suma dintre doua pozitii (care, btw. se poate face mult mai simplu cu AIB :wink: ). evident, actualizarea se va face ceva de genu`: Cod: info[x] = min(info[left], info[right]) acolo unde calculezi sumele, in loc sa zici Cod: suma += info[x] vei zice Cod: minim = min(minim, info[x]) Titlul: Răspuns: 007 Arbori de intervale Scris de: alexjj din Noiembrie 18, 2004, 20:18:24 multzam trebuie sa incerc (si trebuie sa mearga).
Titlul: Răspuns: 007 Arbori de intervale Scris de: alexjj din Noiembrie 20, 2004, 10:49:19 pt. 1... x era simplu (presupun ca pt. asta era codul tau).
deci eu folosesc ceva de genu ' : Citat Arborele va fi pãstrat sub forma unui vector c în care fiecare element i va conþine suma elementelor subsecvenþei <i - 2k + 1, i>, unde k este numãrul zerourilor terminale din reprezentarea binarã a lui i. shi pseudocodul (pt. modificare ) : Citat • Se identificã poziþia elementului care trebuie modificat. • Cât timp poziþia curentã este cel mult egalã cu dimensiunea ºirului: ♦ Se modificã valoarea elementului de pe poziþia curentã. ♦ Se determinã numãrul k al zerourilor terminale din reprezentarea binarã a poziþiei curente. ♦ Noua poziþie se determinã adunând valoarea 2^k la poziþia curentã etc.. dar vreau intre i shi j. shi nu-i dau de cap. Titlul: Răspuns: 007 Arbori de intervale Scris de: Mircea Pasoi din Noiembrie 20, 2004, 13:01:33 Citat din mesajul lui: alexjj pt. 1... x era simplu (presupun ca pt. asta era codul tau). deci eu folosesc ceva de genu ' : Citat Arborele va fi pãstrat sub forma unui vector c în care fiecare element i va conþine suma elementelor subsecvenþei <i - 2k + 1, i>, unde k este numãrul zerourilor terminale din reprezentarea binarã a lui i. shi pseudocodul (pt. modificare ) : Citat • Se identificã poziþia elementului care trebuie modificat. • Cât timp poziþia curentã este cel mult egalã cu dimensiunea ºirului: ♦ Se modificã valoarea elementului de pe poziþia curentã. ♦ Se determinã numãrul k al zerourilor terminale din reprezentarea binarã a poziþiei curente. ♦ Noua poziþie se determinã adunând valoarea 2^k la poziþia curentã etc.. dar vreau intre i shi j. shi nu-i dau de cap. Tu nu faci arbori de intervale, ci arbori indexati binari (cauta in GInfo despre asta sau in handbook-ul de la IOI 2001). Aceasta structura de date poate fi folosita doar pentru suma dintre i si j (Suma[1..j] - Suma[1..i-1]) , nu si pentru minime/maxime. Daca vrei minim/maxim dintre i si j citeste documentul de arbori de intervale din sectiunea Download (a fost curs la lot anul trecut). Titlul: Răspuns: 007 Arbori de intervale Scris de: alexjj din Noiembrie 20, 2004, 15:44:33 multzumesc. materialul citat e din Ginfo shi scria acolo ca operatie de adunare poate fi inlocuita cu minim, maxim etc. ; nu m-am facut clar de la inceput cu arbori indexati binari (sorry).
nici eu nu credeam ca e posibil. Titlul: Răspuns: 007 Arbori de intervale Scris de: Cristian Strat din Noiembrie 20, 2004, 20:01:27 Citat din mesajul lui: alexjj multzumesc. materialul citat e din Ginfo shi scria acolo ca operatie de adunare poate fi inlocuita cu minim, maxim etc. ; nu m-am facut clar de la inceput cu arbori indexati binari (sorry). nici eu nu credeam ca e posibil. asa cum a recunoscut si autorul intr`o intrebare care i-a fost adresata direct de un prieten de al meu, acea precizare este eronata. min(i, j) nu se poate face cu AIB (sau inca nu stie nimeni). |