aib

[•Andreid91]

Pot folosi AIB-uri  querry/update pt minime? (querry pt interval 1-n)  Nu prea stiu sa fac update-ul cand  inlocuiesc valoarea minima din AIB (mi-a trecut prin minte ceva mult prea naspa ~ log^2 ).   

[•toni2007]

Pe aib poti cauta minimul doar pe intervalul (1, x):

Cod:

void update (int poz, int val) {
    for (; poz <= N; poz += lsb(poz))
        aib[poz] = min(aib[poz], val);
}

Si query-ul :

Cod:

int query (int poz) {
    int ret = inf;
    for (; poz; poz -= lsb(poz))
        ret = min(ret, aib[poz);
    return ret;
}

[•Andreid91]

Ok...numai ca in pb-ma apare si cazul in care trebuie sa sterg un element din AIB (il initializez cu  infinit ). Eu daca trebuie sa elimin chiar elementul minim din aib (si sa inlocuiesc cu valoarea infinit), ce valoare pun in AIB[poz] ?  Cum fac update-ul mai exact? Nu credk merge tot aib[poz]=min(aib[poz],val) pt ca valoarea aib[poz] e minimul vechi care trebuie sters, iar val este de fapt infinit...  Sper ca ma intelegi

Mie mi se pare destul de dubios. Credk finalizez cu AI pana la urma