007 Arbori de intervale

[•nash]

Am incercat sa fac cu AIB-uri. Nu realizez insa ce am gresit...
Folosesc doi vectori , unul pentru AIB si unul pentru numere .
Cand fac update modific vec[] ... punand noul element, apoi pun in AIB maximul dintre noul element si query( P - ZERO(p) , p-1 ) - adica maxim pana la elementul respectiv.
Apoi iau toate intervalele care cuprind acel element si fac update .

query() - merg de la "b" la "a" . Cand intervalul curent depaseseste capatul "a" .. nu ma uit in AIB ci direct la numarul de acolo si fac maximul cu rezultatul momentan apoi reiau AIB-ul de la urmatorul element. altfel.. iau maxiumul dintre ce am deja si ce este in AIB.

Este normal sa imi depasesca timpul... dar nu inteleg de ce da rezultat gresit.

http://infoarena.ro/job_detail/466835

[•toni2007]

Nu poti face query de maxim pe aib, pentru ca o sa ai maximul pe intervalul (1, b), nu pe intervalul (a, b).

[•blasterz]

Ba poti!

Uite sursa:

http://infoarena.ro/job_detail/245035?action=view-source

[•nash]

Normal ca poti...   Trebuie doar sa ai putina atentie la modul cum gandeste... citeste ce am scris eu... a mai fost discutat pe topicul acesta ... , evident complexitatea creste log^2N

[•toni2007]

Si de ce ai face asa ? Complexitatea e mai proasta, de scris scri mai mult, ... 

[•nash]

Pentru ca practic se comporta mai bine ( este mai  cache-friendly ) chiar daca complexitatea e mai mare  + pentru ca se poate + pentru ca vreau sa vad cum merge + pentru amorul artei + ca sa ma aflu in treaba, sirul ar putea continua...
 Dupa cum spuneam, s-a mai discutat pe subiectul acesta chiar in acest topic. ( citeste prima pagina ). Nu cred ca scrii mai mult...

Later edit:
  Am gasit eroarea, era o problema de un indice :d
http://infoarena.ro/job_detail/467671

Sursa ia decat 40p datorita faptului ca update-ul meu face doua query-uri si chiar daca complexitatea este tot log^2(n) dubleaza constanta . Am vazut ca se poate doar cu un singur apel de query() dar nu realizez cum se face asta. Poate sa explice cineva?

O optimizare care se poate face tine de initializarea vectorului care se poate face in O(n) fata de O( nlog^2(n) ) prin update-uri repetate.
http://infoarena.ro/job_detail/467686

Plus diferenta care duce de la 70p la 100p
http://infoarena.ro/job_detail/467851

[•nash]

Se poate face query() si update() pentru max/min pentru secvente in logn ? ( cu AIB-uri )

[•S7012MY]

De ce in sursa oficiala dimensiune e 4*dim+66 si nu 2*dim-1 ?

[•nash]

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 ( 218 ).
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 2ceil(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.

In mod evident ar fi putut sa aleaga 2*n elemente. Dar ar fi fost mai urat la implementare ( ar fi trebuit sa aiba grija cu ultimul nivel din arbore ) . A ales forma aceea ca sa fie sigur ca numarul este suficient de mare cat sa intre in cea mai mica valoare mai mare sau egala cu 2*n care sa fie putere a lui 2 ( in mod cert ar fi putut sa o calculeze )

[•livium]

Eu nu pot sa inteleg cum se reprezinta valorile din exemplu 4 3 5 6 1, ca un arbore de intervale.
 
Poate cineva sa-mi zica cum sunt asezate aceste valori in vectorul care memoreaza arborele?

Eu stiu si cum functioneaza un heap, dar aici nu-mi pot da seama.
Va multumesc!

[•PlayLikeNeverB4]

Nu sunt reprezentate valori, ci (cum spune si numele) intervale. Daca luam A ca arborele de intervale, atunci el va arata cam asa:

A[1] (1,5) = 6 -maximul intregului sir
A[2] (1,3) = 5
A[3] (4,5) = 6
A[4] (1,2) = 4
A[5] (3,3) = 5
A[6] (4,4) = 6
A[7] (5,5) = 1
A[8] (1,1) = 4
A[9] (2,2) = 3

Edit: LoL... telepatie
P.S.: Acum ca ma uit mai atent...si se scrie "Fiii"

[•gabitzish1]

Desi a mai postat cineva inainte, scrisesem si eu mesajul si poate te ajuta si ce'am scris eu

notam asa : [x,y](z) - intervalul x -> y are valoarea maxima z
[1,5](6) -radacina. Fii lui sunt [1,3](5) si [4,5](6)
[1,3](5) are fii [1,2](4) si [3,3](5)
[1,2](4) are fii [1,1](4) si [2,2](3)
[4,5](6) are fii [4,4](6) si [5,5](1)

Observi ca valorile citite se afla in frunze (adica in intervale de lungime 1 [x,x]). Pentru a construi arborele se pleaca din frunze.

[•livium]

Gata, am inteles.
Piuhh, greu de tot query-ul ala de inteles. Mi-a ars multi neuroni.

[•Bit_Master]

Mai mariti limitele de timp un pic.
50 cu scanf, 100 cu fstream.

[•gabitzish1]

100 cu scanf : http://infoarena.ro/job_detail/146448?action=view-source
sunt bune limitele.

[•darkseeker]

Poate cineva sa-mi explice cum se face update-ul cand se sterge un element dintr-un interval ? M-am izbit de acest lucru la problema zeap . Nu am gasit alta solutie decat a decala toate elementele spre stanga ...

[•pauldb]

Depinde ce operatie vrei sa faci. Daca vrei minim, pui infinit, daca vrei maxim, pui -infinit, daca vrei suma, pui 0, etc.

E mai bine sa pui intrebarile privind problemele din arhiva in topicul lor.

[•darkseeker]

Multumesc pentru raspuns si imi cer scuze pentru offtopic dar in topicul problemei respective era inactiv din 2008 si m-am gandit ca nu imi va raspunde nimeni . Mai am o intrebare ... o voi adresa tot in acest topic deoarece nu este neaparat legata d vreo problema anume . Am un sir d elemente si ma intereseaza maximul pe un interval la fiecare moment . Daca ar trebui sa sterg al 3-lea si al 4-lea element si as pune -infinit in locul lor apoi as interoga pentru intervalul [3,4] nu mi-ar -infinit ? Sau ar trebui sa consider ca pozitiile respective din sir devin inaccesibile ?

[•PlayLikeNeverB4]

Daca te referi la faptul ca dupa eliminarea pozitiilor 3 si 4, a treia si a patra pozitie vor deveni 5 si 6, atunci trebuie sa afli mai intai pentru un interval [a,b] pozitia celui de-al a-lea termen dupa eliminare si la fel pentru b si apoi faci query intre pozitiile aflate. Deci, pe exemplul tau vei face query pe [5,6].
Sper ca am inteles bine intrebarea ta.

[•SebiSebi]

Cum pot sa cresc valorile dintr-un interval [a,b] cu o constanta val in O(log n)? Multumesc anticipat!

[•devilkind]

Tii o informatie suplimentara in fiecare nod, reprezentand valoare pe care ai adunat-o pe tot intervalu respectiv. Acuma cand faci un update, daca ai ajuns la un nod al carui interval asociat este inclus in intervalul [a, b] atunci updatezi valoarea respectiva, si atentie, NU mai continui recursvitatea in jos de acolo.

[•SebiSebi]

Da, dar pe urma nu pot sa inteleg cum aflu maximul pe un interval. Daca poti sa imi scrii un cod sa inteleg mai bine.
Procedura de actualizare din articolul doamnei Lica ar arata cam asa ( sa spunem ca dorim marirea valorilor din intervalul [a,b] cu 5 ) :

void update(int nod, int st, int dr)
{
   int mij;
   if((a<=st)&&(dr<=b)) {
      MaxArb[nod]=MaxArb[nod]+5;
      return;
   }
   else {
      mij=(st+dr)/2;
      if(a<=mij)
         update(2*nod,st,mij);
      if(mij<b)
         update(2*nod+1,mij+1,dr);
      MaxArb[nod]=MaxArb[nod]+5;
   }
}

Gresesc undeva, dar nu imi dau seama unde.

[•pauldb]

Tu gresesti pentru ca cresti maximul indiferent daca esti sau nu in interval (datorita instructiunii cu + 5 in else).

Daca vrei ca apoi sa obtii maximul pe intreg sirul, functia ar trebui sa fie ca mai jos. Daca vrei sa faci query-uri de maxim pe anumite intervale, atunci trebuie sa faci lazy update si lucrurile devin mai complicate.

Cod:

void Update(int update_left, int update_right, int value, int left, int right, int node) {
	if (update_left <= left && right <= update_right) {
		add[node] += value;
		maxim[node] += value;
	} else {
		int mid = (left+right) / 2;
		if (update_left <= mid) {
			Update(update_left, update_right, value, left, mid, node*2);
		}
		if (update_right > mid) {
			Update(update_left, update_right, value, mid+1, right, node*2+1);
		}
		maxim[node] = max(maxim[node*2], maxim[node*2+1]) + add[node];
	}
}

[•informatician28]

Nu stiu ce se intampla.. Am facut o sursa la problema asta pe care eu o consider corecta si i-a 0 pct.
In final am testat si sursa oficiala care i-a 0 pct:
http://infoarena.ro/job_detail/664311?action=view-source

Need HELP!!!

[•klamathix]

Din functia de query:

Cod:

	else if(div < finish) Query(2*nod+1,div+1,right);

Esti sigur de chestia asta? Gandeste-te un pic. Also, gandeste-te un pic si la cratime .