BOJ 15724州指数

https://www.acmicpc.net/problem/15724
2秒、512 MBメモリ
input :

N, M(1 ≤ N, M ≤ 1,024)

N行にはM個の整数があり、単位領域内のユーザ数は

である.

K(1 ≤ K ≤ 100,000)

x1, y1, x2, y2(x1 ≤ x2, y1 ≤ y2).

output :

矩形範囲内の人口総数、出力

これは2 D部分の累積を計算する一般的な問題です.
BOJ 20002りんごの木
同じアルゴリズムを用いる問題には多くの問題がある.
他の部分はありません.2 D配列を考えてインデックスを移動するだけです.
2 Dセクションと
このスライドを見るのはいい方法かもしれません.
注意すべき点は、入力されたインデックスが1から始まるため、この部分を自分のdp配列と比較する必要があることです.

import sys

n, m = map(int, sys.stdin.readline().split())
graph, dp = [], [[0] * (m + 1) for _ in range(n + 1)]

for _ in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    graph.append(temp)

for x in range(1, n + 1):
    for y in range(1, m + 1):
        dp[x][y] = dp[x - 1][y] + dp[x][y - 1] - dp[x - 1][y - 1] + graph[x - 1][y - 1]

k = int(sys.stdin.readline())
for i in range(k):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    print(dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1])