simontoth, Tuesday common C++ interview problem: O(1) region sum.
Given a 2D grid of integers, provide a method that calculates the sum of a sub-region:
- int64_t Grid::region_sum(Coord top_left, Coord bottom_right) const;
The methods must operate in O(1). You are allowed preprocessing and O(|grid|) memory.
Solve it yourself: https://compiler-explorer.com/z/nxvqrqfWq
Solution: https://compiler-explorer.com/z/31GMbscxT