2D Prefix Sum

二维前缀和 1. 问题场景：从一维到二维 我们先回忆一下一维前缀和。给你一个数组 arr，如果频繁地问你 arr[L...R] 的和，我们会预处理一个前缀和数组 preSum，其中 preSum[i] = arr[0] + ... + arr[i]。这样 sum(L, R) 就可以用 preSum[R] - preSum[L-1] 在 O(1) 时间内得到。 现在，我们把问题升级到二维： 给你一个二维矩阵 matrix，现在会非常频繁地问你：以 (r1, c1) 为左上角，以 (r2, c2)...