with an O(nm) preprocessing the queries will take O(1) for each cell x,y find sum[x,y] which is sum of all elements in rectangle with coordinates (0,0) (x,y) . this can be done in O(nm) (using inclusion-exclusion principle) sum[x,y] = a[x,y] + sum[x-1,y] + sum[x,y-1] - sum[x-1,y-1]
now for each query (x1,y1) (x2,y2) the result is sum[x2, y2] - sum[x1-1, y2] - sum[x2, y1-1] + sum[x1-1, y1-1] -- 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.
