question is based on simple D.P. use an auxiliary matrix to record the sum of all rectangles we are possible and use this matrix in subsequent quering there is an example 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
this is our original matrix now keep on doing the sum on auxiliary matrix aux[i][j]=aux[i-1][j]+aux[i][j-1]+original[i][j] this is the relation . hope this helps correct me if i m wrong. On Tue, Dec 14, 2010 at 2:52 PM, juver++ <[email protected]> wrote: > O(nm) preprocessing is required. > A[i][j] contains sum of all numbers which lies into a rectangle with bottom > right corner at (i, j). > To answer the query: decompose rectangles and find the answer via some > addition and subtractions. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
