Range Sum Add/ Lookup Data Structure

[•skipy]

Tot incerc de cateva zile sa scot o structura de date care sa poate face urmatoarele operatii in timp O(log^2(N) sau mai bine...

1) Adauga X la toate elementele de pe un interval
2) Calculeaza suma tuturor elementelor de pe un interval

Am incercat cu arbori de intervale, dar cred ca cu unul singur nu merge.

"Multzam fain" pt orice ajutor

[•silviug]

Daca vectorul e static merge cu arbore de intervale. Pastrezi in fiecare nod adaosul pe intervalul respectiv.

[•skipy]

In ce sens sa fie vectorul static? Ai mereu N elemente, dar evident isi modifica valorile.

Nu prea merge asa. Contraexemplu:
Ai in arbore de intervale 3 noduri: 1, 2, 3.
Intervalele asociate sunt:
1 -> [1..2]
2 -> [1]
3 -> [2]

Adaugi +3 la intervalul [1] si o sa arate arborele asa: 0, 3, 0. Cand interoghezi intervalul [1..2] iti va intoarce 0.

M-am chinuit destul de mult pe foaie si cu o implementare a unui arbore de intervale in care ti 2 valori, dar nu mi-a iesit nimic.

[u-92]

eu garantez ca se poate face cu 2 arbori de intervale chestia asta.. insa problema e acum la un concurs si cred ca ar fi mai bine sa discutam detaliile dupa

[•svalentin]

Se poate face cu arbori de intervale.. (doar le tot implementez de ceva timp si imi ies..)
Cred ca tu iti construiesti arborele gresit!
pt n=3 ai intervalele
[1,3]
[1,2] [3,3]
[1,1] [2,2] X X

--> ai nodul principal [1..N]
--> fii lui [x,y] sunt [x, (x+y) div 2] [(x+y) div 2+1, y]

apoi ca sa obtii ce iti propui tu, iti trebuie 2 valori care sa le tii minte intr-un nod: suma totala a elementelor din intervalul [x..y] si valoarea adaugata per element expliciti intervalului [x..y]
deci daca vreau sa adaug 2 pe intervalul [1,2] (N=3), adaug la suma nodului [1,3] 4, iar la valoarea pe element la [1,2] 2
cand fac querry pe [2,2], trec prin [1,2] si adaug la rezultat acea valoare per element, apoi, daca e cazul adaug si suma din [2,2]

.. nu pot sa explic prea bine in scris, dar cred ca ti-ai facut o idee, mai incerci pe foaie

[VladS]

O alternativa e structura de date prezentata in articolul lui Mircea cu smenuri. Are complexitate mai mare ( sqrt(N) ) dar e mai usor de implementat si inteles.