Până la urmă am luat 100 cu arbori de intervale + parsare 

Salut.
La query verific de fiecare dată când intru în funcție dacă intervalul curent (cLeft, cRight - capete) se cuprinde în totalitate în intervalul dorit (left, right - capete) și returnez suma de pe interval în caz afirmativ. Apoi verific dacă nu se cuprinde deloc și returnez 0 în caz afirmativ. Apoi dacă se cuprinde parțial, îl sparg în 2 intervale și e adevărat că lansez unele apeluri degeaba, dar dacă vede că nu are loc o intersecție între intervale, îmi returnează 0 și nu continuă mai departe.
La update dacă poziția e cuprinsă în intervalul curent, iar intervalul nu e de forma left == right, îl sparg în 2 intervale. Dacă intervalul e de forma left == right, mai fac o verificare să văd dacă sunt pe poziția bună, adun valoarea și mă opresc. Apoi de la frunză, mă duc înapoi și adaug val la toate intervalele prin care am trecut ca să ajung la frunză.

Am mai trimis o modificare acum, unde vizitez doar subarborele care îmi trebuie și am folosit operații pe biți la înmulțirile/împărțirile cu 2. Însă... tot TLE și e ciudat că am luat 100 pe sursa anterioară luna trecută. Dacă parcurgeam tot arborele, aveam O(N^2 + M*N) și asta sigur nu intra în timp.

Mulțumesc pentru răspuns 

Problema se poate face cu arbori de intervale? Am tot încercat să văd de ce o persoană ia TLE cu structura asta de date, dar acum văd că și sursa pe care am luat eu 100 ia TLE pe toate testele. Dacă n-am greșit la implementare, complexitatea e de O(NlogN + MlogN). Ar trebui să ruleze în ~0.0015 secunde, iar limita e 0.15.