intrebare..

[cristi8]

am citit intr-un articol GInfo la vectori de sume (sa aflii suma intre i si j cu s[j]-s[i-1]) :

"Din nou, algoritmul este acelaºi dacã operaþia de însumare
este înlocuitã cu o alta (calcularea produsului, stabilirea
minimului etc.)."

cum se poate adapta pentru a calcula minimul dintr-o subsecventa ?

[•domino]

am citit intr-un articol GInfo la vectori de sume (sa aflii suma intre i si j cu s[j]-s[i-1]) :

"Din nou, algoritmul este acelaºi dacã operaþia de însumare
este înlocuitã cu o alta (calcularea produsului, stabilirea
minimului etc.)."

cum se poate adapta pentru a calcula minimul dintr-o subsecventa ?

Algoritmul de acolo nu se poate adapta decat daca iti trebuie minimul pentru intervale de forma [1..x]

[•svalentin]

Algoritmul acela nu il poti adapta!
dar daca te intereseaza, poti incerca cu RMQ
dar iti trebuie preprocesare O(NlogN) memorie si afli raspunsul la min dintre x si y in O(1) (asta ca sa iti faci o idee daca merita sa te interesezi de algoritm!)

[•Cosmin]

Poti face si cu un arbore de intervale preprocesare si memorie O(n) si query O(log n).

[cristi8]

aa.. si inca ceva... unde gasesc mai multe informatii despre structuri de date pe net ? ..ce e fiecare, cand o poti folosi, si explicatia lor (si detalii de implementare)

[•svalentin]

daca gasesti sa-mi spui si mie!!

[•andrei202]

Am si eu o intrebare ... pentru o suma de genu pow(1,1) + pow(2,2) + ...+ pow(n,n) exista vreo formula am nevoie pentru o problema in care trebuie sa calculez suma asta