Problem link - The Timber Auction
Problem Statement
The GoC Timber Mafia is notorious for its deforestation activities in the forests near Siruseri. These activities have increased multifold after the death of the bandit who used to lord over these jungles. Having lost the battle to prevent the Mafia from illegally felling the teak trees in this forest, the government of Siruseri came up with a novel idea. Why not legalise the deforestation activity and at least make some money in the process? So the Government decided to lease out parts of the forest to the Timber Mafia.
Most of the teak trees in the forests of Siruseri were planted during the colonial times, after the native trees had been cut. Like everything European, the forest is very regular and orderly. It is rectangular in shape and the trees are arranged in uniformly spaced rows and columns.
Since the trees differ in height and girth, the timber value differs from tree to tree. The forest department has collected data on each tree and knows the volume of wood (in cubic feet) available in each tree in the forest.
Approach
The goal is to calculate the total timber value in a given rectangular subregion of the forest efficiently. To achieve this, a prefix sum array is used for every row in the forest. The prefix sum for a row stores the cumulative sum of timber values from the first column to any given column in that row. This allows quick computation of the sum of timber values in any rectangular region, as the sum of values for a segment of a row can be derived by subtracting the prefix sum at the start of the segment from the prefix sum at the end of the segment.
For a given query that specifies the boundaries of a rectangular region, the prefix sums for all rows in the specified range are used to compute the sum of timber values in constant time for each row. Summing these row-wise values gives the result for the entire rectangular region.
Time Complexity
Building the prefix sums takes O(N×M), and processing each query is O(N), where N is the number of rows, M is the number of columns, and q is the number of queries.
Space Complexity
The space required is O(N×M) for storing the prefix sums.