How to find maximum xor in a sub matrix?

Question

eg given 3 x 3 matrix

   1 2 3
   4 5 6
   7 8 9

has max xor value = 15 sub matrix

   2 
   5 
   8

that is column matrix having index 1

For 1D array trie is a possible approach but cant think of any approach for 2D array

Answer 1

A straight-forward solution is

1. Enumerate all possible row ranges (upper bound and lower bound)

2. For each range, vertically sum up the rows in the range to one row. Say we are working on the example in the question, and we are trying to find the maximum xor in a sub matrix that starts from Row2 and ends at Row3. Then we can vertically sum up 4 5 6 and 7 8 9 to

   4 xor 7 5 xor 8 6 xor 9 = 3 13 15

3. use the algorithm for 1D array. In the example, we can find the maximum xor sum of 7 8 9 is 15, which represents the sub matrix

   6
   9
   

This would be a O(n^3log(max value)) solution.

Answer 2

One way to speed up a brute force try-all-possibilities approach is to find a way of working out the result of an arbitrary sub-matrix without xorring together all its elements. You can do this if you prepare a table where the entry at T(x, y) is the xor of all elements (i,j) where i <= x and j <= y, as you can then calculate any sub-matrix by xorring together four elements.

Now if you want the answer for e.g. the submatrix M(3-10, 5-23) you should find that it is T(10, 23) ^ T(2, 23) ^ T(10, 4) ^ T(2, 4)

The first term covers all of the elements you want, but includes those with i and j values too low. The second term removes those with i values too low. The second term removes those with j values too low, but also does a double removal of those with both i and j values too low. The final term corrects for this double removal.

You can also think of this as an application of the principle of inclusion-exclusion (https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle) or draw yourself a picture showing four overlapping rectangles co-operating to draw a submatrix.

Answer 3

You can use https://en.wikipedia.org/wiki/Fenwick_tree for fast xor calculation and updates. Segment tree is another structure that can be used. It has similar characteristics but uses more memory. Both can be used for 1D array case as well.