Diferente pentru blog/square-root-trick intre reviziile #71 si #70
Nu exista diferente intre titluri.
Diferente intre continut:
h2. Range Sum bq.. Given A, an n elements array, implement a data structure for point updates and range sum queries:
- set(i, x): A[i] :=x,
- set(i, x): A[i] := k,
- sum(lo, hi) returns A[lo] + A[lo+1] + .. + A[hi]. p. The naive solution uses an array. It takes $O(1)$ time for an update and $O(r-l) = O(n)$ for the range sum.
