考察点:前缀和数组 pre[i]=arr[0..i-1] 的构造与查询 sum(l,r)=pre[r+1]-pre[l];把每次区间求和从 O(n) 降到 O(1);二维前缀和的容斥公式。属简答题。
要点:
pre[0]=0,pre[i]=pre[i-1]+arr[i-1];则区间 [l, r] 的和 = pre[r+1] - pre[l]。构造 O(n),单次查询 O(1),适合「多次区间求和」场景。pre[i][j] 表示左上角 (0,0) 到 (i-1,j-1) 的矩形和,构造用容斥: pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1];
任意子矩阵和同样用四角容斥 O(1) 取出,常用于图像/网格题。
pre[0]=0 的偏移写法可避免大量 -1 边界判断,是工程首选。题目与答案就在本页;收藏、批注和错题重练在应用内