星星博客 »  > 

二维前缀和模板

// 预处理前缀和数组
{
    sum.resize(n+1, vector<int>(m+1,0));
    // 预处理除前缀和数组(模板部分)
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            // 当前格子(和) = 上方的格子(和) + 左边的格子(和) - 左上角的格子(和) + 当前格子(值)【和是指对应的前缀和,值是指原数组中的值】
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
        }
    }
}
    
// 首先我们要令左上角为 (x1, y1) 右下角为 (x2, y2)
// 计算 (x1, y1, x2, y2) 的结果
{
    // 前缀和是从 1 开始,原数组是从 0 开始,上来先将原数组坐标全部 +1,转换为前缀和坐标
    x1++; y1++; x2++; y2++;
    // 记作 22 - 12 - 21 + 11,然后 不减,减第一位,减第二位,减两位
    // 也可以记作 22 - 12(x - 1) - 21(y - 1) + 11(x y 都 - 1)
    ans = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];

}

相关文章