首页 > 代码库 > Mobile phones_二维树状数组
Mobile phones_二维树状数组
【题意】给你一个矩阵(初始化为0)和一些操作,1 x y a表示在arr[x][y]加上a,2 l b r t 表示求左上角为(l,b),右下角为(r,t)的矩阵的和。
【思路】帮助更好理解树状数组。
#include<iostream>#include<stdio.h>#include<string.h>using namespace std;const int N=1050;int c[N][N];int s;int lowbit(int x){ return x&(-x);}void update(int x,int y,int a){ for(int i=x;i<=s;i+=lowbit(i)) { for(int j=y;j<=s;j+=lowbit(j)) { c[i][j]+=a; } }}int get_sum(int x,int y){ int sum=0; for(int i=x;i>0;i-=lowbit(i)) { for(int j=y;j>0;j-=lowbit(j)) { sum+=c[i][j]; } } return sum;}int main(){ int ins; int x,y,a; int l,b,r,t; while(scanf("%d",&ins)) { if(ins==0) { scanf("%d",&s); memset(c,0,sizeof(c)); } else if(ins==1) { scanf("%d%d%d",&x,&y,&a); update(x+1,y+1,a); } else if(ins==2) { scanf("%d%d%d%d",&l,&b,&r,&t); l++,b++,t++,r++; printf("%d\n",get_sum(r,t)+get_sum(l-1,b-1)-get_sum(r,b-1)-get_sum(l-1,t)); } else break; } return 0;}
Mobile phones_二维树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。