有没有该题型Python模版？求

Question

查找矩阵的任意子矩阵，并求满足条件（最小值 <= 子矩阵和 <= 最大值）的子矩阵的个数
如何通过算法（类似于：二分+前缀和）优化，使复杂度降低
只会写一维的

import bisect
a = [1,3,5,7,9,4,2]
lower, upper = 0, 13
pre_sum = 0
ans = 0
order = [0]  # 有序列表：储存已经出现的前缀和
for i in a:
    pre_sum += i
    l = bisect.bisect_left(order, pre_sum - upper)
    r = bisect.bisect_right(order, pre_sum - lower)
    ans += r - l
    bisect.insort(order, pre_sum)
print(ans)

Answer 1

引自免费微信小程序：皆我百晓生

要解决这个问题，我们可以创建一个 Python 函数，它接受一个二维矩阵、一个最小值和一个最大值作为参数。这个函数会遍历矩阵中的所有可能子矩阵，检查它们的和是否在给定的范围内，然后统计符合条件的子矩阵数量。

首先，我们需要定义一个辅助函数，用于计算矩阵中某个子矩阵的和。接着，我们将使用两个嵌套循环遍历矩阵，每次移动一个窗口大小为 (r, c) 的子矩阵，并调用辅助函数计算其和。然后我们检查子矩阵和是否在指定范围内，如果是，则增加计数器。

以下是完整的 Python 代码实现：

def sum_of_submatrix(matrix, r, c):
    # Calculate the sum of a submatrix with top left corner at (i, j)
    i, j = 0, 0
    total_sum = 0
    for _ in range(r):
        for _ in range(c):
            total_sum += matrix[i][j]
            j += 1
        i += 1
        j = 0
    return total_sum

def count_satisfying_submatrices(matrix, min_sum, max_sum):
    rows, cols = len(matrix), len(matrix[0])
    count = 0

    # Check all possible submatrices with size (r, c) where 1 <= r, c <= len(matrix)
    for r in range(1, rows + 1):
        for c in range(1, cols + 1):
            for i in range(rows - r + 1):
                for j in range(cols - c + 1):
                    sub_matrix_sum = sum_of_submatrix(matrix, r, c)
                    if min_sum <= sub_matrix_sum <= max_sum:
                        count += 1

    return count

# Example usage:
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

min_sum = 10
max_sum = 15

result = count_satisfying_submatrices(matrix, min_sum, max_sum)
print(f"Number of satisfying submatrices: {result}")

这段代码首先定义了一个 sum_of_submatrix 辅助函数，用于计算子矩阵的和。接下来，count_satisfying_submatrices 函数通过四个嵌套循环遍历所有可能的子矩阵，并使用 sum_of_submatrix 函数计算每个子矩阵的和。如果子矩阵和在给定范围内，就增加计数器。最后，返回满足条件的子矩阵数量。

在这个例子中，我们使用了一个简单的 3x3 矩阵和范围从 10 到 15。运行此代码将输出满足条件的子矩阵数量。您可以根据实际需求更改输入矩阵和范围。