PROBLEM LINK:
Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh
DIFFICULTY:
EASY
PREREQUISITES:
2-D Array, Static Array Queries, Prefix Sum
PROBLEM:
We are given a 2-D array A of size N*M, followed by Q queries. In each query, we are given two coordinates (a, b) and (x, y) and we need to find the sum of the elements of the grid between the given coordinates, i.e. within the range (a, b), (a, y), (x, b) and (x, y) inclusive.
QUICK EXPLANATION:
We can solve this problem by constructing a 2-D prefix sum array that can be used to calculate the sum of any rectangular subarray in O(1) time. Each sum in the array corresponds to a subarray that begins at the upper-left corner of the array.
EXPLANATION:
Here the number of queries is very large, hence finding the sum of the elements from (a, b) to (x, y) everytime will cause a TLE. So we need to process the queries efficiently. We can use a prefix sum array for this purpose. Each entry in the array corresponds to the sum of the subarray that begins at the upper-left corner of the array upto that position. This way we can calculate the sum of any rectangular subarray in O(1) time.
In order to build the prefix sum array, we can iterate through the PRE array in order and calculate the sum as PRE[i, j] = PRE[i, j-1] + PRE[i-1, j] – PRE[i-1, j-1] + A[i, j].
Now, to find the sum of the rectangular subarray starting from (a, b) upto (x, y) we can simply find the value of sum = PRE[x, y] – PRE[x, b-1] – PRE[a-1, y] + PRE[a-1, b-1].
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here.