Skip to content

Files

Latest commit

author
Shuo
Nov 27, 2021
cb30580 · Nov 27, 2021

History

History

sum-of-special-evenly-spaced-elements-in-array

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Nov 27, 2021

< Previous                  Next >

Related Topics

[Array] [Dynamic Programming]

Hints

Hint 1 Think if y cannot be small. You can solve a query in O(n/y), so if y is large enough, it won't be a problem.
Hint 2 If y is small, like less than B, you can preprocess the answers for all such ys in O(n * B), then answer each such query in O(1).
Hint 3 As you might have already guessed, the optimal value for B is ~sqrt(n).