Daily bit(e) of C++ | O(1) region sum
Daily bit(e) of C++ #191, Common interview problem: O(1) region sum.
Today we will look at a common C++ interview problem: O(1) region sum.
Given a 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 method must operate in O(1); however, you are allowed preprocessing and O(|grid|) additional memory.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/nxvqrqfWq.
Solution
First, let’s consider a simpler problem with only one dimension. How can we return the sum of contiguous elements in a 1D array in O(1)?
For example, given an array {5,2,3,0,1,4}, let’s say we want to calculate the sum of elements on indexes {3..5}. We know that Sum({3..5}) is the same as Sum({0..5})-Sum({0..2}). Since we are allowed preprocessing, we could calculate all prefix sums, allowing us to return any sum in O(1).
Extending this idea into 2D is straightforward; we only need to be careful about overlapping regions and handle them properly.
If we follow the approach from the 1D version, we will end up with precomputed sums for each coordinate, where the sum represents the area {0, 0}..{row, col}. We can then calculate the sum of the blue region by subtracting the two overlapping red-green regions and adding back the green region.
