首页 > 代码库 > 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_二维树状数组