You are not logged in. Please login at www.codechef.com to post your questions!

×

# GRIDGM – Editorial

Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh

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.

This question is marked "community wiki".

asked 08 Oct '18, 15:13

3436
accept rate: 21%

19.8k350498541

 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×218
×94
×83
×4
×4
×4
×4

question asked: 08 Oct '18, 15:13

question was seen: 180 times

last updated: 11 Oct '18, 17:17