打鼹鼠

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1162 字

二维树状数组子矩阵和

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1540
// 题意：n×m 零矩阵，操作 1 x y k 使 A[x][y] 自增 k；操作 2 a b c d 求左上 (a,b) 右下 (c,d) 子矩阵和。n,m≤2^12，操作数≤3e5，|k|≤1e5。
// 思路：二维树状数组。单点加、二维前缀和查询，子矩阵和用容斥。
// 复杂度：O(操作数 · log n · log m) 时间 / O(nm) 空间
// 易错点：下标 1 基；子矩阵和容斥 (S(c,d)-S(a-1,d)-S(c,b-1)+S(a-1,b-1))；和可能超过 int 用 long long。
#include <bits/stdc++.h>
using namespace std;
#include <vector>
using namespace std;
int N, M;
vector<vector<long long>> bit;
void add(int x, int y, long long v){
    for(int i=x;i<=N;i+=i&-i)
        for(int j=y;j<=M;j+=j&-j) bit[i][j]+=v;
}
long long sum(int x, int y){
    long long s=0;
    for(int i=x;i>0;i-=i&-i)
        for(int j=y;j>0;j-=j&-j) s+=bit[i][j];
    return s;
}
int main(){
    if(!(cin>>N>>M)) return 0;
    bit.assign(N+2, vector<long long>(M+2,0));
    while(true){
        int op;
        if(!(cin>>op)) break;
        if(op==1){
            int x,y; long long k;
            cin>>x>>y>>k;
            add(x,y,k);
        } else if(op==2){
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            long long ans=sum(c,d)-sum(a-1,d)-sum(c,b-1)+sum(a-1,b-1);
            cout<<ans<<"\n";
        } else break;
    }
    return 0;
}

打鼹鼠

正文

一本通·提高篇的其它内容