【模板】二维树状数组 & LOJ #133 二维树状数组 1

题面

题目链接

这是一道模板题。

给出一个  的零矩阵 ,你需要完成如下操作:

  • 1 x y k:表示元素  自增 ;
  • 2 a b c d:表示询问左上角为 ,右下角为  的子矩阵内所有数的和。

思路

一维树状数组的扩展

我们知道,一维树状数组可以求一段区间的和,将其扩展到二维,对于一个矩阵,每一层可以看做一个数,实际上是树状数组,每次求到每一层时求出这一层的区间和即可。也就是两个一维树状数组套一套。

容斥思想

通过和树状数组一样的思路可以求出原点到目标点的子矩阵的和,和二维前缀和相同,利用容斥思想就可以求出任意子矩阵的和。具体如图,右下角浅色子矩阵的面积可以通过面积相减得到。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,s[5000][5000];
int lowbit(int x){
    return -x&x;
}
void updata(int x,int y,int z){
	for (int i=x;i<=n;i+=lowbit(i)){
		for (int j=y;j<=m;j+=lowbit(j)){
			s[i][j]+=z;
		}
	}
}
long long getsum(int x,int y){
	long long res=0;
	for (int i=x;i>0;i-=lowbit(i)){
		for (int j=y;j>0;j-=lowbit(j)){
			res+=s[i][j];
		}
	}
	return res;
}
int main(){
	cin>>n>>m;
    int x,a,b,c,d;
    while(cin>>x){
        if(x==1){
        	cin>>a>>b>>c;
            updata(a,b,c);
        }else{
        	cin>>a>>b>>c>>d;
            cout<<getsum(c,d)-getsum(a-1,d)-getsum(c,b-1)+getsum(a-1,b-1)<<endl;
        }
    }
}

 

暂无评论

发送评论 编辑评论


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