问题链接在这里。问题基本上是计算给定大小 N 乘 M 矩阵的所有此类子矩阵，其元素总和介于 A 和 B 之间。N,M<=250。10^-9<=A<=B<=10^9。
人们已经使用DP和BIT解决了它。我不清楚如何。
首先，我试图解决上述问题的一个更简单的版本，一维情况：给定一个长度为 N 的数组 A，计算所有子数组，其中子数组中的元素总和位于 A 和 B 之间，但仍然不能认为比 O(n^2) 更好。这是我所做的：
我想制作另一个数组来保留原始数组的前缀和，比如前缀 [N]。前缀[i] = A 1 + A[2] + A[3] + ...A[i]。设置前缀[1] = A [1]。然后对于从 2 到 N 的每个 i，问题是计算所有 j <= i 使得总和 Z = A[j] + A[j+1] + ..A[i] 位于 A 和 B 之间。这是等价的到前缀[i] - 前缀[j-1]。但它仍然是 O(n^2)，对于每个 i，j 都在 i 位置。
任何人都可以帮助我逐步推进我解决主要问题的给定方法吗？