Problema clasică

Se dă un vector $v$ cu $n$ elemente naturale, indexat de la $1$. Asupra lui se vor face $m$ operații, codificate astfel:

• $0$ $st$ $dr$ – Să se determine suma pe intervalul $[st, dr]$ ($v_{st} + v_{st+1} + \cdots + v_{dr}$).

• $1$ $pos$ $val$ – Să se schimbe valoarea elementului de pe poziția $pos$ în $val$.

Metode de rezolvare

1) Naivă: Folosim un vector în care pe fiecare poziție reținem valoarea elementului corespunzător.

2) Sume parțiale: Folosim un vector în care pentru fiecare prefix reținem suma elementelor până la poziția respectivă: $sum_i = v_1 + v_2 + \cdots + v_i$.