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 qu
You have given a matrix of n*m integer. A query will come to you with two
co-ordinate (x1,y1) (x2,y2). You need to find sum of all elements which
falls inside rectangle. As you will be bombarded with such query, you
solution should be very very quick.
Ans should be in O(1)
Regards,
Akash Agrawa
