2-D Analog to Segement Trees?

Jason Yang

The main problem of our project was investigating whether or not there was an efficient 2D analog to the segment tree. Here, instead of updating and querying arbitrary ranges of a list of numbers, we want to update and query arbitrary submatrices of a matrix of numbers. When updating a submatrix, we add all numbers in the submatrix with an arbitrarily chosen constant value; when querying a submatrix, we find the minimum of all numbers in the submatrix. We wanted to see whether there was a data structure that could efficiently perform each of these operations being repeatedly done one after the other, where each update can affect future queries. The answer we found to this question is a conditional no if a specific long-standing conjecture is assumed. The conjecture is the “All-Pairs Shortest Path Conjecture”, which states that the “All-Pairs Shortest Path” problem cannot be solved in “truly subcubic” time. Since at least the 1970s, it has been known that the “All-Pairs Shortest Path” problem has equal difficulty to computing a certain operation on matrices, called “min-plus matrix multiplication”, which is similar to the standard matrix multiplication in linear algebra but where the summation is replaced with the minimum() function and the multiplication is replaced with addition. Also since the 1970s, this conjecture has remained open, and not too much progress has been made towards refuting it. The key to achieving our research result was realizing that if there was an efficient 2D segment tree, then it could perform min-plus matrix multiplication in truly subcubic time, which would refute the conjecture. Therefore, if the conjecture is true, which many believe to be the case, then an efficient 2D segment tree is impossible.