직사각형 합 (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}$$