2次元区間和

常識的に考えたらこんな感じではいかないなと思うのだけど一応

H, W, N = map(int, input().split())
A = [[int(x) for x in input().split()] for _ in range(H)]
#W*Hの配列に0を入れたものを作る（0の分だけ＋１する）
ans = [[0] * (W + 1) for _ in range(H + 1)]

for i in range(1, H + 1):
    ans[i] = [0] + A[i - 1][:]
    #計算して入れていく（もともとある数字に累積和を入れていくので＋＝になる）
    for j in range(1, W + 1):
        ans[i][j] += ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1]

print(ans)

#指定のものを出力する
for _ in range(N):
    a, b, c, d = map(int, input().split())
    print(ans[c][d] - ans[a-1][b-1])

まあ、ケース１の1番目のように1,1と3,3と、左端から右端なら全部なのでうまくいくけど、
そうでもないところからだとうまくいかない。

とりあえず累積和を出力しておくと

[
[0, 0, 0, 0],
[0, 1, 3, 6],
[0, 5, 12, 21],
[0, 12, 27, 45]
]

なので、
ans(1,1) ans(3,3)の区間だと、図形でいうと全部なので
ans(3,3)＝45になってしまう。
しかし、
ans(1,2)＝３ ans(2,3)＝21だと、２と６の間、つまり２＋３＋５＋６＝16が答えになるのだが
さてどうやって足すか。
。。。と図形を見ながらにらめっこしたが、うまくロジックが取り出せる
図形の引き算ができず、時間がきてギブ。
結論からすると
S({a,b},{c,d}) = S(c,d) - S(a-1,d) - S(c,b-1) + S(a-1,b-1)という関係になるらしい。
実際にやってみると
S(1,1),(3,3) = S(3,3) - S(0,3) - S(3,0) + S(0,0) = 45 - 0 - 0 = 0
S(1,2),(2,3) = S(2,3) - S(0,2) - S(2,1) + S(0,1) = 21 - 5 - 0 = 16
2番目の計算は不思議だけど、
1＋2＋3＋4＋5＋6 - (1 + 2) - (1 + 4) ＋ 1 = 2＋3＋5＋6＝16となるので
不思議ではない。１は−1になるが、結局あとで＋１となり相殺され、1が消える。

H, W, N = map(int, input().split())
A = [[int(x) for x in input().split()] for _ in range(H)]
#W*Hの配列に0を入れたものを作る（0の分だけ＋１する）
ans = [[0] * (W + 1) for _ in range(H + 1)]

for i in range(1, H + 1):
    ans[i] = [0] + A[i - 1][:]
    #計算して入れていく（もともとある数字に累積和を入れていくので＋＝になる）
    for j in range(1, W + 1):
        ans[i][j] += ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1]
    
for _ in range(N):
    a, b, c, d = map(int, input().split())

    val = ans[c][d]
    if 0 < a and 0 < b:
        val += ans[a - 1][b - 1]
    if 0 < a:
        val -= ans[a - 1][d]
    if 0 < b:
        val -= ans[c][b - 1]

    print(val)