Pagini recente » Diferente pentru blog/square-root-trick intre reviziile 102 si 72 | Diferente pentru blog/square-root-trick intre reviziile 102 si 64 | Diferente pentru problema/gugustiuc intre reviziile 44 si 43 | Diferente pentru blog/square-root-trick intre reviziile 102 si 83 | Diferente pentru blog/square-root-trick intre reviziile 21 si 22
Nu exista diferente intre titluri.
Diferente intre continut:
The range sum query is interesting. Slices completely contained in our range are summed up fast. The elements of the first and last slice (partially contained in the queried range) have to be traversed one by one.
!<{margin-right: 20px; auto;display:block;border: 1px solid gray;}blog/square-root-trick?image00.png!
The code looks like this:
== code(c) |
i = l
sum += a[lo]
==
!<{margin-right: 20px; auto;display:block;border: 1px solid gray;}blog/square-root-trick?image00.png!
The query takes less than <tex>k + n/k + k = 2k + n/k</tex> time. 2k + n/k is minimized when k ~ sqrt(n). For k = sqrt(n) the query takes O(sqrt(n)) time.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
