007 Arbori de intervale

[•DITzoneC]

Aici puteti discuta despre problema Arbori de intervale.

[•mugurelionut]

Misto ideea cu arhiva educationala. Anyway, daca tot ati atins subiectul arborilor de intervale, as vrea sa propun, in scop educational, sa facem (si m-as implica si eu aici, daca va fi cazul) niste probleme care pun in evidenta mai bine ceea ce pot face arborii de intervale. M-am lovit de cateva ori de situatia in care elevi care ziceau ca stiu bine arbori de intervale nu au reusit sa ii extinda pentru a suporta niste query+update-uri mai "smechere". De exemplu, pare "inradacinata" ideea ca update-ul sau query-ul sunt aplicate pe un interval, iar operatia cealalta este aplicata asupra unui element (adica: update pe interval si query pe element sau update pe element si query pe interval).

Arborii de intervale sunt mult mai flexibili si suporta cel putin urmatoarele 4 situatii care apar prin probleme:

* creste valoarea fiecarui element dintr-un interval cu x (update) si intreaba care e suma elementelor dintr-un interval (query)
* creste valoarea fiecarui element dintr-un interval cu x (update) si intreaba care e minimul/maximul elementelor dintr-un interval (query)
* seteaza valoarea fiecarui element dintr-un interval la x (update) si intreaba care e suma elementelor dintr-un interval (query)
* seteaza valoarea fiecarui element dintr-un interval la x (update) si intreaba care e minimul/maximul elementelor dintr-un interval (query)

Nu o sa mai mentionez utilizarea altor tipuri de update-uri si query-uri (de exemplu, bazate pe operatii pe biti sau query-uri pentru minimul sumelor partiale sau pentru subsecventa de suma maxima - ultima problema aflandu-se si in arhiva infoarena).

[•devilkind]

desi nu are legatura cu arbori de intervale, ar fi frumos sa se dea niste punctaje partiale (si sa fie mentionata in "indicatii de rezolvare" ) si ideea cu impartirea in bucati de sqrt(n) a vectorului.

[•filipb]

Ar fi foarte utile problemele pe care le-ai specificat. Am completat tabelul (nu am stiut cum sa trec mai concis, am scris arbori de intervale aplicatie 1, etc ).
Am adaugat problema separata pentru bucati de sqrt N.

[•Cosmin]

Ar merge puse operatii de update diferite ca sa tinem tot in acelasi loc. Practic fiecare problema e un articol, nu are rost sa le dispersam prea tare.

[•raduzer]

Cred ca limita de timp ar putea fi scazuta la 0.3 sec. Cu toate ca nu e chiar asa de important, ca daca face cineva cu arbori de intervale oricum intra in 0.3, iar daca face brut iese din 0.4...

[•Cosmin]

Cartesian tree se poate face in O(n) ... si nu iti trebuie arbori de intervale. Poti citi rezolvarea in cartea lui Catalin Francu.

[•amadaeus]

Vad ca solutia cu AIB-uri pentru maxime pe intervale, de complexitate teoretica O(log² N) pe update si query, se comporta mai bine in practica decat cea cu arbori de intervale (cu O(log N) pe fiecare operatie). Cel putin in implementarile mele

[•wefgef]

Nu doar in implementarile tale . AIB ruleaza!

[•gogu]

un AIB e mult mai cache-friendly decat un arbore de intervale.
cum in ultimii ani viteza procesoarelor a crescut mult mai repede ca viteza memoriilor, e din ce in ce mai important cache-ul.

Stiu ca multi din cei ce fac jocuri pentru Xbox / PS3 transforma in array-uri simple multe structuri de date avansate mai rapide asimptotic dar care sparg des cache-ul pentru ca au procesoare foarte rapide dar RAM mult mai incet.

In concluzie, folositi varianta in O(sqrt(N))

http://infoarena.ro/job_detail/154183

[•CezarMocan]

Stiti vreun articol mai pe intelesul tuturor in legatura cu cacheul? Ca nu prea inteleg cum sta treaba cu asta...

[•gogu]

As baga eu un articol despre cache si ceva optimizari in general, daca se ofera cineva sa-l formateze frumos.

[•stef2n]

Da, sigur. Hai ca ma ocup eu de aspect. Redacteaza-l.

[•runnaway90]

 
Stiu ca a fost prezentat acum cativa ani la Lot ceva legat de cache ... ( sper sa nu ma insel ) ...

[•vizitator]

Cum pot creste la un arbore de intervale in care retin minimul de ex. toate elementele dintr-un interval cu un anumit numar (update-ul) ?

[•toni2007]

 in o(n)...

gandeste-te ca tu tre sa faci update si la frunzele din arbore (elem cele mai de jos, la care intervalul are doar un elem) si pierzi pe alea o(n)

[•vizitator]

la O(n) ma gandeam si eu....da e cam mare limita


am vazut si o problema pe infoarena......biscuiti......la care trebuie facut update pe un interval, si nu incape daca faci in O(n)

[•astronomy]

Se poate O(logN), sunt mai multe detalii chiar in forum la problema biscuiti.

[•vladiana]

cum pot face sa folosesci un vector de numa 2*n-1 elemente? ce conditii trebuie sa pun in plus? normal un arbore de intervale are numa 2*n-1 noduri.....

[•Prostu]

cum pot face sa folosesci un vector de numa 2*n-1 elemente? ce conditii trebuie sa pun in plus? normal un arbore de intervale are numa 2*n-1 noduri.....

Cand declari tabloul in care tii arborele de intervale, acesta nu trebuie sa aibe dimensiunea 2*n, ci mai degraba cea mai mica valoare mai mare sau egala cu 2*n care este si putere a lui 2. Adica pentru un n = 100000, ar trebui sa declari tabloul de 262144 ( 2¹⁸ ).
Asta datorita codificarii pe care o faci nodurilor si a faptului ca arborele tau nu este un arbore complet binar. Pe penultimul nivel nu toate nodurile o sa aibe 2 noduri ca fii, ci multe o sa aibe un singur fiu. Indicile nodului curent poate insa sa ajunga pana la 2^{ceil(log(n))+1}-1, pentru ca arborele are ceil(log(n)) + 1 niveluri.
Asta se intampla in cele mai multe implementari, si in sursa ta, poti sa folosesti si numai 2*n noduri, insa codificarea lor este mult mai dificila.

[•florin_marius90]

salut . ce optimizari pot sa fac la nivel de program pascal ca sa mi iasa in timp, pt imi depasheshte timpu cu 0.02, si nush ce sa fac. plus ca treaba e relativa, pe aceiashi sursa iau punctaje diferite, plus ca la unele teste timpul in care iese programu e mai mic decat cel impus de problema si totushi imi zice timp depashit...... 

si inca ceva : in pascal daca declaram un vector de intregi. si apoi il afisham pe ecran de ex, fara a face nici o modificare asupra lui. sau nu neaparat un vector: normal ar trebui sa apara valoarea nula adica 0 nu?  ms

[•philip]

Au fost schimbate testele la problema asta?
Rezolvarea mea (in pascal) nu reuseste nicicum sa intre in timp.
Am reintrodus si niste surse mai vechi, tot in pascal, care au luat 100 p cu cateva luni in urma, si nici ele nu scot mai mult de 50 p.


LE: Trebuia folosit "shl" si "shr" in loc de "*2", "/2", si in pascal trebuie parsata si citirea, altfel nu intra in timp.

LE2: Inca ceva... La testele 1 si 7 este cate un spatiu (" ") in plus la sfarsitul liniei cu elementele vectorului.

[•alexandru92]

Imi putei spune, va rog frumos, cum as putea rezolva query-ul folosind aib-uri ?

[•Mishu91]

Păi nu prea poți. Cu aib poți face query-uri doar pe intervalul [1, x], iar la minim/maxim nu prea mai merge treaba. Totuși, dacă citești toate posturile acestui topic vei afla că există o abordare a problemei cu aib în O(log²N) pe query.

[•alexandru92]

Totuși, dacă citești toate posturile acestui topic vei afla că există o abordare a problemei cu aib în O(log²N) pe query.

M-am uitat peste sursa lui @Lucian si nu inteleg cum face acel query