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.

*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).
 
Baga si articolul asta http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees care  cred ca e ceva mai bun decat cel al lui Mihai.
 
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.
 

h2. Probleme similare
* 'Datorii':problema/datorii