015 Arbori indexati binar

[•filipb]

Aici puteti discuta despre problema Arbori indexati binar.

[•anna_bozianu]

HELP pls.
Am doua implementari http://infoarena.ro/job_detail/174357 de 50 p in care incerc sa fac operatia de tip 2 in O(log n) si a doua http://infoarena.ro/job_detail/174387 de 100 p in care la operatia de tip 2 gasesc indicele prin cautare binara. Nu reusesc cu nici un chip sa descopar ce gresesc la prima implementare. E sigur ca de la operatia de tip 2 vine greseala cat timp sursele sunt identice in rest. Poate reuseste cineva sa vada unde e greseala.
 Mii de multumiri.

[•Dorin]

Vezi ce afisezi cand cauti pozitia minima k astfel incat suma valorilor primilor k termeni sa fie exact 0.

[•filipb]

Da, de la asta e. Daca k = 0 trebuie afisat -1.

[•anna_bozianu]

Intr-adevar, asa era. Am facut modificarea si a mers. Inca odata multumesc.

[•test_b]

In explicatia de pe ginfo despre aib zice ca pentru suma (a,b) se scad (1,b), si (1,a-1). Dar asta nu merge de exemplu pentru minim ... pentru minim cum se face ?

[•wefgef]

Nu poti folosi arbori indexati binar pentru astfel de query-uri. Trebuie sa folosesti alte structuri de date, cum ar fi arborii de intervale.

[•Marius]

Se poate si cu arbori indexati binar, insa in O(log² n). Cu arbori de intervale ai O(log n).

[•toni2007]

O problema draguta cu aib-uri 2d e Mobiles de la IOI 2001, alta fiind si cutii de pe infoarena.

[•wefgef]

O chestie tare pe care tocmai am descoperit-o:

LSB(x) = x & -x

[•Marius]

O chestie tare pe care tocmai am descoperit-o:

LSB(x) = x & -x

E veche.

[•Mishu91]

Imi poate recomanda cineva un articol despre AIB in 2D si cum se implementeaza, ca din ce am cautat nu am gasit cine stie ce

[•toni2007]

Aib-urile 2d se implementeaza la fel ca cele 1 d doar ca ai doua foruri:

Cod:

void Update(int a, int b, int val){
    int i, j;
    for (i = a; i <= n; i += lsb(i))
        for (j = b; j <= n; j += lsb(j))
           aib[i][j] += val;
}

Uite inca o problema pe ideea asta: http://www.spoj.pl/problems/MATSUM/. De asemenea, vazusem cateva pe z-trening tot asa.

Spor

[•Mishu91]

Mersi fain

[•Marius]

Imi poate recomanda cineva un articol despre AIB in 2D si cum se implementeaza, ca din ce am cautat nu am gasit cine stie ce

Mobiles, IOI 2001

[•toni2007]

E si pe spoj problema, se poate testa rezolvarea acolo https://www.spoj.pl/problems/NKMOBILE/

[•philip]

O chestie tare pe care tocmai am descoperit-o:

LSB(x) = x & -x

E veche.

In tutorialul de pe topcoder se explica cum s-a ajuns la relatia asta.
Dar nu inteleg egalitatea de la care s-a pornit: Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1.
De ce opusul unui numar este egal cu "negatia" + 1?

[•Prostu]

In tutorialul de pe topcoder se explica cum s-a ajuns la relatia asta.
Dar nu inteleg egalitatea de la care s-a pornit: Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1.
De ce opusul unui numar este egal cu "negatia" + 1?

Trebuie sa privesti problema din punctul de vedere al masinii, unde x este un sir binar. Asa sunt reprezentate de calculatoare numerele negative, se numeste reprezentare complementara si are importanta proprietate ca nu trebuie examinati bitii de semn la adunarea sau scaderea a doua numere.
http://cs.ubbcluj.ro/~rlupsa/edu/ac/doc/repr-intr.html
http://en.wikipedia.org/wiki/Two%27s_complement

[•stocarul]

Se pot executa cele 3 tipuri de operații în O(log₂N) și cu un arbore de intervale.
Sursa: http://infoarena.ro/job_detail/370470?action=view-source

[•sima_cotizo]

Se pot executa cele 3 tipuri de operații în O(log₂N) și cu un arbore de intervale.
Sursa: http://infoarena.ro/job_detail/370470?action=view-source

Ce spui tu este cunoscut, insa arborii indexati binar au avantajul spatiului: folosesti doar N elemente (in loc de 4N cat e la arborii de intervale). In plus, mi se pare ca sunt ceva mai rapizi pe operatiile pe care le implementeaza, dar se poate sa fie doar o parere

[•stocarul]

Ce spui tu este cunoscut, insa arborii indexati binar au avantajul spatiului: folosesti doar N elemente (in loc de 4N cat e la arborii de intervale). In plus, mi se pare ca sunt ceva mai rapizi pe operatiile pe care le implementeaza, dar se poate sa fie doar o parere

Știam că este cunoscut, numai că în "descrierea soluției" nu am văzut nimic legat de acest lucru.
Iar referitor la memorie, cred că sunt necesari doar 2N la arborii de intervale.

[•wefgef]

Arborii indexati binar sunt mult mai rapizi decat arborii de intervale, asa ca va recomand sa ii folositi de fiecare data cand puteti.

Legat de memoria folosita de un aint, daca N = 33 cat se aloca? 

[•nash]

O problema ciudata... la problema asta daca pun "inline" in fata functiei "search" .. iau 0 puncte cu raspuns incorect , daca scot  inline de la cautarea binara... iau 100 ...   , probleme cu compilatorul ?

http://infoarena.ro/job_detail/463335
http://infoarena.ro/job_detail/463334

[•wefgef]

Daca schimbi denumirea functiei iti merge? Cred ca e un name clashing cu o functie din algorithm.

[•nash]

Am schimbat ... dar daca pun inline ... aceasi problema
http://infoarena.ro/job_detail/463342

Oricum... daca erau doua functii cu aceasi signiatura ar fi trebuit sa dea o eroare ( ambiguitate .... ) Mie imi compileaza fara nici o eroare .  + "inline" nu schimba signiatura functiei ...