직사각형 합 (2차원 누적합)

문제

$R$행 $C$열의 정수 격자 $A$가 주어진다. 그리고 $Q$개의 질의가 들어온다. 각 질의는 네 정수 $r_1, c_1, r_2, c_2$ ($0 \le r_1 \le r_2 \le R-1$, $0 \le c_1 \le c_2 \le C-1$)이며, $(r_1, c_1)$부터 $(r_2, c_2)$까지의 직사각형 영역에 들어 있는 모든 칸 값의 합을 구하는 일이다.

2차원 누적합

$P_{i,j}$를 "왼쪽 위 $(0,0)$부터 $(i-1, j-1)$까지의 직사각형 합"이라 정의한다. 이를 점화식으로 계산하면:

$P_{i,j} = P_{i-1,j} + P_{i,j-1} - P_{i-1,j-1} + A_{i-1,j-1}$

겹치는 부분 $P_{i-1,j-1}$을 한 번 빼 줘야 한다 (포함-배제).

그러면 $(r_1, c_1)$부터 $(r_2, c_2)$까지 직사각형 합은:

$\text{rect\_sum} = P_{r_2+1,c_2+1} - P_{r_1,c_2+1} - P_{r_2+1,c_1} + P_{r_1,c_1}$

제한

• $1 \le R, C \le 1000$
• $1 \le Q \le 10^5$