Let me take a 3x5 board for the example (numbers written in base 10):

1 2 4 3 6

8 6 2 1 3

9 3 7 2 4

If you want to get hash value of sub-board (2, 2) to (3, 4), you can get the hash value of the string 6|2|1|0|0|3|7|2 (the character | not appear in the real string, I just put it to seperate the numbers).

That string can be built by start at cell (2, 2), read from left to right, top to bottom to cell (3, 4). If you meet a cell which doesn't lie inside the sub-board, you assign it value 0.

So what you need is calculate H(i, j) is the hash value from (1, 1) to (i, j). Then for query (x1, y1), (x2, y2) you can use H to calculate the answer easily.

Sorry for my bad English.

I haven't done many problems of this kind but probably you can use an idea similar to string hashing by considering the characters in the sub-board in the row major order and constructing a string using that and then hashing that string. Firstly, for two sub-boards, we must consider their sizes. If their sizes are different, then the sub-boards are also different. Otherwise, use hashing.

You extend 1d hashed to 2d the same way you extend 1d prefix sums to 2d. You just need to take different vertical and horizontal base.

For table:

and bases p and q, hash table will look like:

You calculate it this way:

And to get hash of an area you use: