Răspuns: 007 Arbori de intervale

[alexjj]

Question : Cum modific algoritmul de determinare a sumei dintre doua pozitii a unui vector (care foloseste evident arbori de intervale) ca sa calculez minimul ?. (Mentionez ca nu vreau sa mi sa raspunda cu USE RMQ, e pe info.devnet).

Thank you for reading this !

[•wickedman]

Daca ai nevoie de minim intre 1 si X poti folosi foarte usor AIB.
Daca iti trebuie intre i si j trebuie sa modifici foarte putin algoritmul ce determina suma dintre doua pozitii (care, btw. se poate face mult mai simplu cu AIB   ).

evident, actualizarea se va face ceva de genu`:

Cod:

info[x] = min(info[left], info[right])

acolo unde calculezi sumele, in loc sa zici

Cod:

suma += info[x]

vei zice

Cod:

minim = min(minim, info[x])

[alexjj]

multzam trebuie sa incerc (si trebuie sa mearga).

[alexjj]

pt. 1... x era simplu (presupun ca pt. asta era codul tau).
deci eu folosesc ceva de genu ' :

Arborele va fi pãstrat sub forma unui vector c în care
fiecare element i va conþine suma elementelor subsecvenþei
<i - 2k + 1, i>, unde k este numãrul zerourilor terminale din
reprezentarea binarã a lui i.

shi pseudocodul (pt. modificare ) :

• Se identificã poziþia elementului care trebuie modificat.
• Cât timp poziþia curentã este cel mult egalã cu dimensiunea
ºirului:
♦ Se modificã valoarea elementului de pe poziþia curentã.
♦ Se determinã numãrul k al zerourilor terminale din reprezentarea
binarã a poziþiei curente.
♦ Noua poziþie se determinã adunând valoarea 2^k la poziþia
curentã
etc..

dar vreau intre i shi j. shi nu-i dau de cap.

[•domino]

pt. 1... x era simplu (presupun ca pt. asta era codul tau).
deci eu folosesc ceva de genu ' :

Arborele va fi pãstrat sub forma unui vector c în care
fiecare element i va conþine suma elementelor subsecvenþei
<i - 2k + 1, i>, unde k este numãrul zerourilor terminale din
reprezentarea binarã a lui i.

shi pseudocodul (pt. modificare ) :

• Se identificã poziþia elementului care trebuie modificat.
• Cât timp poziþia curentã este cel mult egalã cu dimensiunea
ºirului:
♦ Se modificã valoarea elementului de pe poziþia curentã.
♦ Se determinã numãrul k al zerourilor terminale din reprezentarea
binarã a poziþiei curente.
♦ Noua poziþie se determinã adunând valoarea 2^k la poziþia
curentã
etc..

dar vreau intre i shi j. shi nu-i dau de cap.

Tu nu faci arbori de intervale, ci arbori indexati binari (cauta in GInfo despre asta sau in handbook-ul de la IOI 2001). Aceasta structura de date poate fi folosita doar pentru suma dintre i si j (Suma[1..j] - Suma[1..i-1]) , nu si pentru minime/maxime. Daca vrei minim/maxim dintre i si j citeste documentul de arbori de intervale din sectiunea Download (a fost curs la lot anul trecut).

[alexjj]

multzumesc. materialul citat e din Ginfo shi scria acolo ca operatie de adunare poate fi inlocuita cu minim, maxim etc. ; nu m-am facut clar de la inceput cu arbori indexati binari (sorry).
nici eu nu credeam ca e posibil.

[•wickedman]

multzumesc. materialul citat e din Ginfo shi scria acolo ca operatie de adunare poate fi inlocuita cu minim, maxim etc. ; nu m-am facut clar de la inceput cu arbori indexati binari (sorry).
nici eu nu credeam ca e posibil.

asa cum a recunoscut si autorul intr`o intrebare care i-a fost adresata direct de un prieten de al meu, acea precizare este eronata.
min(i, j) nu se poate face cu AIB (sau inca nu stie nimeni).