After making the aux array (as written in above post), you can answer any query in O(1) time by using the following relation: assuming top left as (x1,y1) and bottom right as (x2,y2)
sum_of_rectangle = aux[x2][y2] - aux[x1-1][y2] - aux[x2][y1-1] + aux[x1-1][y1-1] It may happen that while subtracting 1 from any variable above the value may come out to be negative. That should be handled. Regards. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
