Complexity of Parallelogram Range Minimum Query Given an $n\times n$ array $G$, what is known about the complexity of parallelogram static RMQs?

More formally, answering the query

$$RMQ_P(a,b,c,d)=\min_{a\leq i \leq b \\ c \leq i+j \leq d}G[i][j]$$

In terms of preprocessing, and answering the query where the array is static
This can be reduced to rectangular RMQ in $O(n^2)$ time and space. Create a new array $H$ where $H[i][i+j] := G[i][j]$, padding entries $H[i][k]$ with $k &lt; i$ or $k \ge i + n$ with $\infty$. Run $RMQ(a, b, c, d)$ on $H$ whenever you would run $RMQ_P(a, b, c, d)$ on $G$.

Now run your favorite 2D-RMQ algorithm such as this. Perhaps you want to be very conservative with the extra space used though. In that case I suspect unpacking your favorite result will show that it helps to avoid writing $H$ down, and instead use an $O(1)$ function to produce values of $H$ by lookup into $G$.