Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Circle Sum Queries

Revision en1, by Kognition, 2018-06-02 22:00:59

A friend told me a problem that he had been trying to optimize for a personal graphics project, and it involved having an h × w grid, and wanting to do some pre-processing to answer circle-sum queries. A circle here would be defined as having some center, (yc, xc), where 1 ≤ yc ≤ h and 1 ≤ xc ≤ w and some radius r, and it is the set of integer grid points (y, x) such that (x - xc)2 + (y - yc)2 ≤ r2.

The progress he's made is that in O((hw)2) pre-processing, you can just precompute all the possible queries, so one possible set of complexities is O((hw)2) pre-processing and O(1) queries. Another possibility is to precompute prefix sums in O(hw) time and answer the queries in O(r) time.

Is there any clever way to get a better set of pre-processing and query complexity than the two methods mentioned above?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Kognition 2018-06-02 22:00:59 886 Initial revision (published)