Pagini recente » Atasamentele paginii Profil yulyan | Borderou de evaluare (job #1357759) | Cod sursa (job #758970) | Diferente pentru blog/square-root-trick intre reviziile 16 si 15
Nu exista diferente intre titluri.
Diferente intre continut:
Given an n elements array, implement a data structure for point updates and range sum queries:
- set(i, x): a[i] := k,
- sum(lo, hi) returns a[lo] + a[lo+1] + .. + a[hi].
- sum(l, r) returns a[l] + a[l+1] + .. + a[r]).
The naive solution uses an array. It takes <tex>O(1)</tex> time for an update and <tex>O(r-l) \eq O(n)</tex> for the range sum.
The naive solution uses an array. It takes <tex>O(1)</tex> time for an update and <tex>O(r - l) \eq O(n)</tex> for the range sum.
A more efficient solution splits the array into length k slices and stores the slice sums in an array S.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.