# Matrix multiplication over range in \$O(n)\$

Let $$M$$ denote the time it takes to multiply 2 matrices, and $$Q$$ denote the number of queries.

Is it possible to create a data structure with $$O((n+Q)M)$$ pre-computation time, and can answer range matrix multiplication queries that satisfy $$l_{i-1}\le l_i$$ and $$r_{i-1}\le r_i$$ with an overall time complexity of $$O((n+Q)M)$$. I’ve been thinking a lot on how to manipulate 2 pointers to get the intended results, but haven’t come up with any approach yet. The matrices are not necessarily invertible.