Pagini recente » Diferente pentru blog/square-root-trick intre reviziile 99 si 98 | Diferente pentru blog/square-root-trick intre reviziile 67 si 66 | Diferente pentru blog/square-root-trick intre reviziile 27 si 28 | Diferente pentru blog/square-root-trick intre reviziile 95 si 94 | Diferente pentru blog/square-root-trick intre reviziile 82 si 81
Nu exista diferente intre titluri.
Diferente intre continut:
A more efficient solution splits the array into length $k$ slices and stores the slice sums in an array $S$.
The update takes constant time, because we have to update the value for A and the value for the corresponding $S$.
!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image01.png!
The query is interesting. The elements of the first and last slice (partially contained in the queried range) have to be traversed one by one, but for slices completely contained in our range we can use the values in $S$ directly and get a performance boost.
!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image01.png!
!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image00.png!
p. The code looks like this:
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
