h2. Solutie

O rezolvare brute a problemei ar obtine in jur de 30 puncte si o poti gasi 'aici':job_detail/147500?action=view-source. Solutia optima pentru rezolvare a problemei are complexitate O({$MlogN$}) si se poate realiza prin intermediul 'arborilor indexati binar':problema/aib?action=download&file=aib.pdf. O solutie de 100 puncte pe ideea aceasta gasesti 'aici':job_detail/147499?action=view-source.

O rezolvare brute a problemei ar obtine in jur de 30 puncte si o poti gasi 'aici':job_detail/147500?action=view-source. Solutia optima pentru rezolvare a problemei are complexitate O({$MlogN$}) si se poate realiza in mai multe moduri.
Prima rezovare consta in folosirea 'arborilor de intervale':problema/arbint. O solutie care merge pe ideea aceasta gasesti aici:job_detail/147552.
A doua solutie se realizeaza intermediul 'arborilor indexati binar':problema/aib?action=download&file=aib.pdf, care foloseste mai putina memorie O(N). O solutie de 100 puncte pe ideea aceasta gasesti 'aici':job_detail/147499?action=view-source.

*Feedback Cosmin:* ar mai trebui adaugat un tip de query care este ignorat de obicei si e destul de util: gasirea elementului i astfel ca suma de a[j] 1 <= j <= i sa fie egala cu k. Aceasta operatie se poate implementa naiv cu cautare binara in O(log^2 n) dar te poti folosi de structura arborelui ca sa o faci in O(log n).

Si baga si paperul original http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

Mentioneaza ca se pot generaliza in mai multe dimensiuni, si ca de obicei daca ai k dimensiuni atunci ei folosesc max^k spatiu, dar daca folosesti un hash map vor folosi n * log^k max spatiu, unde max e coordonata maxima si n e numarul de querieuri/updateuri. Cred ca e explicat ceva despre chestia asta in articolul meu de cautari ortogonale.

Mentioneaza ca se pot generaliza in mai multe dimensiuni, si ca de obicei daca ai k dimensiuni atunci ei folosesc max^k^ spatiu, dar daca folosesti un hash map vor folosi n * log^k^ max spatiu, unde max e coordonata maxima si n e numarul de querieuri/updateuri. Cred ca e explicat ceva despre chestia asta in articolul meu de cautari ortogonale.

h2. Probleme similare