Summed Area Table
Suppose you have a very large matrix A and you would like to calculate the sum of a submatrix that resides within A. How would you do that?
It would be relatively straightforward, if you had do it just once. You would sum up all the elements in that submatrix which would be of O(m*n) time complexity, where m is the number of rows and n is the number of columns in the submatrix. The question becomes a bit more complex if you have to query the sum of different submatrices multiple times. Unsurprisingly, such use-cases do come up in Computer Vision and Computer Graphics, and O(m*n) time complexity can get incredibly disturbing for repetitive calls.