Meta 高频算法真题：用 2D 前缀和快速统计子矩形中 1 的数量

# Given a large rectangular 2D grid of arbitrarily-placed 1's and 0's, write a service that answers
# the query "how many 1's in a given subgrid?". You should assume that the grid is large, doesn't
# change, and is given to you ahead of time. The query will be called many times, so it needs to be fast.

# Example
# Grid:
# 0 0 0 1
# 1 0 1 0
# 1 1 1 0

# int getOnes(x1, y1, x2, y2)

# Input: 0, 0, 1, 3
# Output: 3

# Input: 1, 1, 2, 3
# Output: 3

这是上一题的一维升级版，解法是构建二维前缀和 pre[i][j] 表示从 (0,0) 到 (i,j) 子矩形中 1 的个数。任意子矩形查询都可以用四次查表加加减减在 O(1) 时间得到。主要考察二维前缀和公式推导与边界处理

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Meta、Google、Amazon 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Stripe 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。