015 Arbori indexati binar

[•nash]

 Arbori indexati binar se pot utiliza in calcularea min/max la fel ca si arborii de intervale. Mai important, exista solutie in logN amortizat folosint arbori indexati binar.
 
Practic, cele doua structuri de date sunt la fel de puternice !

[•wefgef]

Cum faci? Ai link către un articol?

[•nash]

Modific modul in care lucreaza update() si query().
Cand o sa am un link de la articol o sa il postez aici.

[•wefgef]

Poți detalia puțin? Sunt foarte curios cum faci pentru că mi-am pus și eu de mult timp problema asta și nu am găsit nicio soluție.

[•S7012MY]

o aplicatie frumoasa http://acm.timus.ru/problem.aspx?space=1&num=1470

[•a_h1926]

Sunt curios daca a incercat cineva sa implementeze AIB-uri cu update pe intervale (nu se adauga valoarea v la elementul de pe pozitia x, ci la toate elementele curinse intre pozitiile x si y), iar daca da, as aprecia daca mi-ar explica si mie cum a facut. Multumesc anticipat.

[•ctlin04]

Poate cineva sa imi explice ideea care efectueaza oparatia 2 in log_n, eu lucrez in pascal si am facut in log^2_n dar asa iau TLE pe ultimile trei teste 

[•dutzul]

hmm se poate uita cineva pe sursa mea iau 40 de pcte cu tle pe restu desi nu cred ca iau tle chiar pe 6 teste am facut solutia cu cautare binara oare de la aia e problema?

Editat de admin: Scrie corect, te rog.

[•costyv87]

Daca avem si elemente de 0 , cum facem cautarea pentru pozitia minima tot in log ?

[•PlayLikeNeverB4]

Exact la fel. Nu te opresti cand gasesti un element cu suma identica, ci lasi cautarea pana la capat.

[•costyv87]

Nu cred ca merge pentru testul urmator :
n= 8
0 1 1 0 1 0 0 0
Cautare pozitia minima pentru suma = 3

La primul pas , o sa verifice exact T[8] = 3 si deja asta inseamna ca valoarea pe care o caut eu e cel putin egala cu 8 .

[•PlayLikeNeverB4]

Cum adica la primul pas 8? Nu ceva gen (1 + n) / 2 ? Sau poate nu inteleg eu ce vrei sa spui. In cazul in care gasesti un element identic mergi pe intervalul din stanga.

[•costyv87]

Daca fac cum zici tu , atunci am un log pentru cautarea binara si inca un log pentru calculul sumei partiale , asta inseamna log^2. eu voiam in log simplu.

[•PlayLikeNeverB4]

Ah, scuze. Probabil merge o varianta putin modificata a functiilor prezentate aici http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#find

[•Maarcell]

E posibil de facut operatia de tipul 2 cu arbori de intervale in O(log n)?

[•SebiSebi]

Da.

[•Maarcell]

Da.

Extrem de informativ. Un indiciu macar?
Scap de cautare binara sau gasesc suma 1..i in O(1)?

[•klamathix]

În principiu simulezi căutarea binară pe arbore. Dacă tu vrei să obții suma A, iar fiul stâng al rădăcinii are suma B >= A te duci în fiul stâng și continui căutarea, altfel o continui în fiul din dreapta pentru valoarea A - B.

Înțeleg că răspunsul pe care l-ai primit anterior nu te-a ajutat (deși tehnic ți s-a răspuns la întrebare), dar încearcă să fii mai politicos. Nu are niciun sens să fii sarcastic când ceri ajutor.

[•Maarcell]

În principiu simulezi căutarea binară pe arbore. Dacă tu vrei să obții suma A, iar fiul stâng al rădăcinii are suma B >= A te duci în fiul stâng și continui căutarea, altfel o continui în fiul din dreapta pentru valoarea A - B.

Înțeleg că răspunsul pe care l-ai primit anterior nu te-a ajutat (deși tehnic ți s-a răspuns la întrebare), dar încearcă să fii mai politicos. Nu are niciun sens să fii sarcastic când ceri ajutor.

Thanks. Cam problematica aceasta operatie.

[•SebiSebi]

Da.

Extrem de informativ. Un indiciu macar?
Scap de cautare binara sau gasesc suma 1..i in O(1)?

Îmi cer scuze că nu am detaliat răspunsul. Am crezut că vrei să știi doar dacă se poate rezolva în O(log N). Nu am vrut să îți stric plăcerea de a găsi o rezolvare, crezând că vrei să știi doar dacă are sens să te gândești la acea complexitate.

[•bugy]

Salutare,

Cred că limita de memorie pentru Java este un pic cam strânsă.

[•sulzandrei]

in loc de x&-x puteti pune x-(x&(x-1))

[•TrascaAndrei]

O problema interesanta cu arbori indexati si de intervale s-a dat anul trecut la InfoOltenia.
Se gasesc aici problemele : http://mircea.unet.ro/io2015.zip