二维区域和检索
中等美团前缀和
题目描述
给定一个二维整数矩阵 matrix，处理多个查询：计算以 (row1, col1) 为左上角、(row2, col2) 为右下角的子矩阵元素之和。使用二维前缀和技巧，预处理每个位置到原点的矩形和，查询时利用容斥原理在 O(1) 时间内得到结果。
示例
输入:
matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]], row1=2, col1=1, row2=4, col2=3输出:
8solution.ts
输出结果
点击「运行代码」按钮查看结果...