[前缀和] – 子矩阵的和

思想概括及问题描述

子矩阵和问题的描述给你一个二维矩阵,如何快速求出其中的子矩阵的和

可以利用前缀和的思想,对于每一个坐标都求出一个到左上角原点的求和矩阵,然后利用推到出的公式即可求出子矩阵的和。

前缀和一般分为两步,就算是矩阵的前缀和也不例外:

  1. 推导前缀矩阵
  2. 利用公式对子区间进行求和

公式

前缀矩阵每一个坐标的推导公式(其中 q 是题目所给的未经过处理的原矩阵):

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + q[i][j]

子区间的查询公式(假如需要查询[x1][y1]-[x2][y2]这个矩阵区间的求和值):

Sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

原题链接和代码

题目:796. 子矩阵的和 – AcWing题库

#include <iostream>
using namespace std;

int m, n, q;
const int N = 10005, M = 1005;
// n 行

int arr[N][M];
// 原矩阵数组
int qrr[N][M];
// 处理后的查询数组

int main() {
    // cin >> n >> m >> q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            scanf("%d", &arr[i][j]);            
        }// 输入原矩阵
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            qrr[i][j] = qrr[i-1][j] + qrr[i][j-1] - qrr[i-1][j-1] + arr[i][j];
        }// 得到处理后的前缀矩阵
    }
    
    while (q --) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", qrr[x2][y2] - qrr[x1-1][y2] - qrr[x2][y1-1] + qrr[x1-1][y1-1]);
    }
    return 0;
}
作者:Sy_
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇