精华内容
下载资源
问答
  • 二维树状数组

    2013-06-11 10:48:27
    它是ACM中关于二维树状数组方面的资料。。
  • 其实,要明确的一点是,不管是一维还是二维树状数组,都只是工具而已,只是帮助我们更快地求和,查询,树状数组的这些操作都可以用我们平常的方法求,例如一直加。面对一个二维数组,我们要求它们的和,会怎么做呢?...

    上一篇讲的是一维数组的树状数组,可以实现“单点修改,区间查询”,“区间修改,单点查询”,“区间修改,区间查询”。

    今天接触二维树状数组。

    其实,要明确的一点是,不管是一维还是二维树状数组,都只是工具而已,只是帮助我们更快地求和,查询,树状数组的这些操作都可以用我们平常的方法求,例如一直加。

    面对一个二维数组,我们要求它们的和,会怎么做呢?

    先求出第一行的总和

    再求出第二行的总和

    再求出第三行的总和

    ..........

    求出最后一行的总和

    最后就是每一行都加起来,得出来的就是二维数组的总和。

    那我们用树状数组来帮我们 “算快一点” 呢?

    第一行是一个树状数组,区间求和

    第二行是一个树状数组,区间求和

    第三行是一个树状数组,区间求和

    ..........

    最后一行也是树状数组,区间求和

    假如有 100000 行呢?

    那我们把每一行树状数组当做一个值,变成一列,对这一列求和,那不就变成一个一维树状数组了吗

    int sum( int x , int y ){
    	int _y = y ;
    	LL ans = 0 ;
    	while( x ){
    		_y = y ;
    		while( _y ){
    			ans += c[x][_y] ;
    			_y -= lower( _y ) ;
    		}
    		x -= lower( x ) ;
    	}
    	return ans ;
    }

    这是对  1- x , 1-y 所表示的矩阵的求和函数,就是嵌套的一维求和呢

    换个方式看

    LL sum( int *c , int x ){
    	LL ans = 0 ;
    	while( x ){
    		ans += c[x] ;        // 每一行求和
    		x -= lower( x ) ;
    	}
    	return ans ;
    }
    
    int Matrix_sum( int x , int y ){
    	LL ans = 0 ;
    	while( x ){
    		ans += sum( c[x] , y ) ;   // 所有行当做一列,对这一列求和
    		x -= lower( x ) ;
    	}
    	return ans ;
    }
    应该很清楚了吧

    更新操作一样的,也都是一维树状数组的更新,然后每一行再看做一列,还是一维更新

    void update( int x , int y , int add ){
    	int _y = y ;
    	while( x <= N ){
    		_y = y ;
    		while( _y <= N ){
    			c[x][_y] += add ;
    			_y += lower( _y ) ;
    		}
    		x += lower( x ) ;
    	}
    }
    换个方式看
    void update( int *c , int x , int add ){
    	while( x <= N ){
    		c[x] += add ;
    		x += lower( x ) ;
    	}
    }
    
    void Matrix_update( int x , int y , int add ){
    	while( x <= N ){
    		update( c[x] , y , add ) ;
    		x += lower( x ) ;
    	}
    }
    其实都是我们正常对矩阵的求和操作,先求出每一行,再求这些行的总和。树状数组,线段树只是让我们求得更快而已。

    也就可以推广到三维,四维..... N 维,都是树状数组的嵌套。

    贴一道例题:POJ 2155

    对二维数组的求和,求出来的和,如果是偶数,说明被修改回来了,如果是奇数,说明没被改回来

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std ;
    #define LL long long 
    #define lower(x) x&-x
    int N , Q ;
    int c[1002][1002] ;
    
    void update( int x , int y , int add ){
    	int _y = y ;
    	while( x <= N ){
    		_y = y ;
    		while( _y <= N ){
    			c[x][_y] += add ;
    			_y += lower( _y ) ;
    		}
    		x += lower( x ) ;
    	}
    }
    
    int sum( int x , int y ){
    	int _y = y ;
    	LL ans = 0 ;
    	while( x ){
    		_y = y ;
    		while( _y ){
    			ans += c[x][_y] ;
    			_y -= lower( _y ) ;
    		}
    		x -= lower( x ) ;
    	}
    	return ans & 1 ;
    }
    
    int main(){
    	int cases , x1 , y1 , x2 , y2 ;
    	scanf( "%d" , &cases ) ;
    	while( cases-- ){
    		memset( c , 0 , sizeof( c ) ) ;
    		scanf( "%d%d" , &N , &Q ) ;
    		char opt[2] ;
    		while( Q-- ){
    			scanf( "%s" , opt ) ;
    			if( opt[0] == 'C' ){
    				scanf( "%d%d%d%d" , &x1 , &y1 , &x2 , &y2 ) ;
    				update( x1 , y1 , 1 ) ;
    				update( x1 , y2+1 , -1 ) ;
    				update( x2+1 , y1 , -1 ) ;
    				update( x2+1 , y2+1 , 1 ) ;
    			}
    			else{
    				scanf( "%d%d" , &x1 , &y1 ) ;
    				printf( "%d\n" , sum( x1 , y1 ) ) ;
    			}
    		}
    		if( cases ) printf( "\n" ) ;
    	}
    	return 0 ;
    }





    展开全文
  • 树状数组升级版(二维树状数组

    千次阅读 2017-11-01 23:30:31
    二维树状数组详细解释

    我在前面已经介绍过了树状数组的各种操作,但是你会轻易的发现前面我们介绍的树状数组都是一维的,那既然一维可以,那么会不会有二维的树状数组呢?
    答案是肯定的。
    那么我今天就来教大家如何实现二维的树状数组。
    今天我介绍基本的功能:

    1. 对二维数组内某一点加上一个值
    2. 求一原点为一个端点的子矩阵和
    3. 求以二维数组中的两个点为端点的子矩阵和

    我们先来讲讲怎么去表示。(分析字太多了,以下的分析采用南宫逸辰的分析)
    数组A[][]的树状数组定义为:

    C[x][y] = ∑ a[i][j], 其中,
    x-lowbit(x) + 1 <= i <= x,
    y-lowbit(y) + 1 <= j <= y.

    例:举个例子来看看C[][]的组成。
    设原始二维数组为:
     A[][]={{a11,a12,a13,a14,a15,a16,a17,a18,a19},
    {a21,a22,a23,a24,a25,a26,a27,a28,a29},
    {a31,a32,a33,a34,a35,a36,a37,a38,a39},
    {a41,a42,a43,a44,a45,a46,a47,a48,a49}};
    那么它对应的二维树状数组C[][]呢?

    记:
    B[1]={a11,a11+a12,a13,a11+a12+a13+a14,a15,a15+a16,…} 这是第一行的一维树状数组
    B[2]={a21,a21+a22,a23,a21+a22+a23+a24,a25,a25+a26,…} 这是第二行的一维树状数组
    B[3]={a31,a31+a32,a33,a31+a32+a33+a34,a35,a35+a36,…} 这是第三行的一维树状数组
    B[4]={a41,a41+a42,a43,a41+a42+a43+a44,a45,a45+a46,…} 这是第四行的一维树状数组
    那么:
    C[1][1]=a11,C[1][2]=a11+a12,C[1][3]=a13,C[1][4]=a11+a12+a13+a14,c[1][5]=a15,C[1][6]=a15+a16,…
    这是A[][]第一行的一维树状数组

    C[2][1]=a11+a21,C[2][2]=a11+a12+a21+a22,C[2][3]=a13+a23,C[2][4]=a11+a12+a13+a14+a21+a22+a23+a24,
    C[2][5]=a15+a25,C[2][6]=a15+a16+a25+a26,…
    这是A[][]数组第一行与第二行相加后的树状数组

    C[3][1]=a31,C[3][2]=a31+a32,C[3][3]=a33,C[3][4]=a31+a32+a33+a34,C[3][5]=a35,C[3][6]=a35+a36,…
    这是A[][]第三行的一维树状数组

    C[4][1]=a11+a21+a31+a41,C[4][2]=a11+a12+a21+a22+a31+a32+a41+a42,C[4][3]=a13+a23+a33+a43,…
    这是A[][]数组第一行+第二行+第三行+第四行后的树状数组

    好,南宫逸辰分析结束。
    我简单总结一下,说白了,就是每一行都是一个树状数组,
    以行为元素,整个列也是一个树状数组。(这句话请记住,这个思想会贯穿始终)
    既然如此,我相信代码也很快就出来了,接下来我就来给出代码,并进行简单的解释。

    单点修改

    void add(int x,int y,int p){  
        while(x<=n){
            for(int i=y;i<=m;i+=lowbit(i)){
                C[x][i]+=p;
            } 
            x+=lowbit(x);
        }  
    }  

    这个根据我刚刚说的两个树状数组(那句贯穿始终的话),就很容易理解了。
    我们外围循环枚举每一行,内循环在行内进行一维树状数组的单点修改,从而实现二维树状数组的单点修改。

    以原点为一个端点的子矩阵和

    int sum(int x,int y){  
        int result = 0;  
        while(x>0){
            for(int i=y;i>0;i-=lowbit(i)){
                result+=C[x][i];
            }
            x-=lowbit(x);
        }  
        return result;  
    }  

    还是那句贯穿始终的话,外围枚举行,内围则是一维树状数组前几项和。这样就能完成我们的任务了。

    以任意两点为左上和右下两个端点的子矩阵和

    int ask(int x1,int y1,int x2,int y2){
        return sum(x2,y2)+sum(x1-1,y1-1)-sum(x2,y1-1)-sum(x1-1,y2);
    }

    和以为树状数组一样,我们依然借助sum去求。
    但是,我们看到,这个公式似乎很长,别急,别晕,听我解释一边即可明白。
    首先声明,我们保证x2>=x1,y2>=y1
    下面让我们先来看一个图:
    公式解释
    红色的矩形是我们要求的。
    我们这里为了和计算机里二维数组的保持一致,我们把x坐标视为纵坐标。(感谢qie_wei指正我的错误)
    首先sum(x2,y2)很显然是整个大矩形,
    sum(x1-1,y2)和sum(x2,y1-1)则是绿色和黄色的两个矩阵(不含红色边),很明显这是我们不要的,所以我们用大的矩阵减去这两个小矩阵。
    但是,减完以后我们会发现蓝色阴影部分的矩阵被减了两次,很明显减多了,所以我们还需要加上sum(x1-1,y1-1)
    这样就成了我给的公式。

    总结

    不是很难,但改进的很巧妙。
    注意复习,随后我会发一道练习题。

    展开全文
  • 求矩阵和的时候,下标弄错WA了一次... 求矩形(x1,y1) (x2,y2)的sum |sum=sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1) ...二维树状数组讲解:http://blog.csdn.net/u011026968/article/details/38532

    http://poj.org/problem?id=1195

    求矩阵和的时候,下标弄错WA了一次...

    求矩形(x1,y1) (x2,y2)的sum
    |sum=sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)

    二维树状数组讲解:http://blog.csdn.net/u011026968/article/details/38532117

    二维树状数组模板:

    /*==================================================*\
    | 二维树状数组
    | 1、初始化:INIT: c[][]置为0; Row,Col要赋初值
    | 数组下标一定要从1开始!!!!!!!!!
    | 2、sum(i,j) 前i行前j列的和,update(i,j,num)
    | 将(i,j)加上num
    | 3、求矩形(x1,y1) (x2,y2)的sum
    |sum=sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)
    |注意Sum和c 必要的时候用long long
    \*==================================================*/
    const int N = 10000;
    int c[N][N]; int Row, Col;
    inline int Lowbit(const int &x){// x > 0
        return x&(-x);
    }
    int Sum(int i,int j){
        int tempj, sum = 0;
        while( i > 0 ){
            tempj= j;
            while( tempj > 0 ){
                sum += c[i][tempj];
                tempj -= Lowbit(tempj);
            }
            i -= Lowbit(i);
        }
        return sum;
    }
    void Update(int i, int j, int num){
        int tempj;
        while( i <= Row ){
            tempj = j;
            while( tempj <= Col ){
            c[i][tempj] += num;
            tempj += Lowbit(tempj);
            }
            i += Lowbit(i);
        }
    }
    

    poj 1195 代码

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <string>
    #include <iostream>
    #include <cmath>
    #include <map>
    #include <set>
    #include <queue>
    using namespace std;
    
    #define ls(rt) rt*2
    #define rs(rt) rt*2+1
    #define ll long long
    #define ull unsigned long long
    #define rep(i,s,e) for(int i=s;i<e;i++)
    #define repe(i,s,e) for(int i=s;i<=e;i++)
    #define CL(a,b) memset(a,b,sizeof(a))
    #define IN(s) freopen(s,"r",stdin)
    #define OUT(s) freopen(s,"w",stdout)
    
    const int MAXN = 1024 +100;
    ll c[MAXN][MAXN];
    int row,col;
    inline int lowbit(int i){return i&(-i);}
    ll sum(int i, int j)
    {
        int tmpj;
        ll ret=0;
        while(i>0)
        {
            tmpj=j;
            while(tmpj>0)
            {
                ret+=c[i][tmpj];
                tmpj-=lowbit(tmpj);
            }
            i-=lowbit(i);
        }
        return ret;
    }
    
    void update(int i, int j, int v)
    {
        int tmpj;
        while(i<=row)
        {
            tmpj=j;
            while(tmpj<=col)
            {
                c[i][tmpj]+=v;
                tmpj+=lowbit(tmpj);
            }
            i+=lowbit(i);
        }
    }
    
    int main()
    {
        //IN("poj1195.txt");
        int op,n,x,y,v;
        int l,b,r,t;
        while(~scanf("%d%d",&op,&n))
        {
            col=row=n;
            CL(c,0);
            while(~scanf("%d",&op))
            {
                if(op == 3)break;
                if(op == 1)
                {
                    scanf("%d%d%d",&x,&y,&v);
                    update(x+1,y+1,v);
                }
                if(2 == op)
                {
                    scanf("%d%d%d%d",&l,&b,&r,&t);
                    printf("%lld\n",sum(r+1,t+1)+sum(l,b)-sum(l,t+1)-sum(r+1,b));
                }
            }
        }
        return 0;
    }
    


    展开全文
  • 二维树状数组2.ppt

    2021-09-17 21:37:54
    二维树状数组2.ppt
  • 二维树状数组涉及到两种基本操作,修改矩阵中的一个点,查询子矩阵的和 首先是修改点的操作: void update(int x,int y,int z) { for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)) ...

    二维树状数组涉及到两种基本操作,修改矩阵中的一个点,查询子矩阵的和

    首先是修改点的操作:

    void update(int x,int y,int z)
    {
        for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))
            c[i][j]+=z;
    }

    然后是查询子矩阵的和,这里查询的是从左上角到目标点所形成的矩阵的元素和

    int sum(int x,int y)
    {
        int ret=0;
        for(int i=x;i>=1;i-=lowbit(i))
        for(int j=y;j>=1;j-=lowbit(j))
            ret+=c[i][j];
        return ret;
    }

    那么如果我要查具体的一个子矩阵,就需要给出左上角的点和右下角的点的坐标,然后:

                int x1,y1,x2,y2;
                cin>>x1>>y1>>x2>>y2;
                cout<<sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)<<endl;

    就可以了

    下面附上完整的二维树状数组的代码:

     1 #include<iostream>
     2 using namespace std;
     3 const int maxn=1005;
     4 const int maxm=1005;
     5 int n,m;
     6 int q;
     7 int a[maxn][maxm];
     8 int c[maxn][maxm];
     9 int lowbit(int x)
    10 {
    11     return x&(-x);
    12 }
    13 void update(int x,int y,int z)
    14 {
    15     for(int i=x;i<=n;i+=lowbit(i))
    16     for(int j=y;j<=m;j+=lowbit(j))
    17         c[i][j]+=z;
    18 }
    19 
    20 int sum(int x,int y)
    21 {
    22     int ret=0;
    23     for(int i=x;i>=1;i-=lowbit(i))
    24     for(int j=y;j>=1;j-=lowbit(j))
    25         ret+=c[i][j];
    26     return ret;
    27 }
    28 int main()
    29 {
    30     cin>>n>>m;
    31     for(int i=1;i<=n;i++)
    32     for(int j=1;j<=m;j++)
    33     {
    34         cin>>a[i][j];
    35         update(i,j,a[i][j]);
    36     }
    37     cin>>q;
    38     while(q--)
    39     {
    40         int x;
    41         cin>>x;
    42         if(x==1)
    43         {
    44             int y,z,w;
    45             cin>>y>>z>>w;
    46             update(y,z,w);
    47         }
    48         if(x==2)
    49         {
    50             int x1,y1,x2,y2;
    51             cin>>x1>>y1>>x2>>y2;
    52             cout<<sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)<<endl;
    53         }
    54     }
    55     return 0;
    56 }

    接下来我们对二维树状数组进行简单的拓展,将其拓展为修改矩形区间,查询点的二维树状数组

    其实就是把二维差分的思想引入进去,当然,如果不用树状数组直接用二维差分数组也是完全可以的,这个时候修改区间变成了O(1),查询点就变成了O(n),还是需要自己去权衡

    二维树状数组的修改和查询的函数还是完全不用去变的

    修改区间就要这么修改了:

                update(x1,y1,w);
                update(x2+1,y2+1,w);
                update(x2+1,y1,-w);
                update(x1,y2+1,-w);

    这个东西虽然是类比一维情况得来的,但是你不要去想,去在纸上画一画,主对角线端点为正,负对角线端点为负,然后就很显然了

    查询单点的话直接sum(x,y)即可

    这里给出完整的代码:

     1 #include<iostream>
     2 using namespace std;
     3 const int maxn=1005;
     4 const int maxm=1005;
     5 int n,m;
     6 int q;
     7 int a[maxn][maxm];
     8 int c[maxn][maxm];
     9 int lowbit(int x)
    10 {
    11     return x&(-x);
    12 }
    13 void update(int x,int y,int z)
    14 {
    15     for(int i=x;i<=n;i+=lowbit(i))
    16     for(int j=y;j<=m;j+=lowbit(j))
    17         c[i][j]+=z;
    18 }
    19 
    20 int sum(int x,int y)
    21 {
    22     int ret=0;
    23     for(int i=x;i>=1;i-=lowbit(i))
    24     for(int j=y;j>=1;j-=lowbit(j))
    25         ret+=c[i][j];
    26     return ret;
    27 }
    28 int main()
    29 {
    30     cin>>n>>m;
    31     cin>>q;
    32     while(q--)
    33     {
    34         int x;
    35         cin>>x;
    36         if(x==1)
    37         {
    38             int x1,y1,x2,y2,w;
    39             cin>>x1>>y1>>x2>>y2>>w;
    40             update(x1,y1,w);
    41             update(x2+1,y2+1,w);
    42             update(x2+1,y1,-w);
    43             update(x1,y2+1,-w);
    44         }
    45         if(x==2)
    46         {
    47             int x,y;
    48             cin>>x>>y;
    49             cout<<sum(x,y)<<endl;
    50         }
    51     }
    52     return 0;
    53 }

    接下来我们开始介绍运用二维树状数组来修改区间和查询区间

    这个问题的模板题是BZOJ3132,上帝造题的七分钟,原题在网站上已经没有了不知道怎么了

    然后这个是直接把一维树状数组的修改区间和查询区间的操作利用那个推出来的式子运用到了二维树状数组上面

    保持二维树状数组的大体形式不做任何改变,只在修改和查询上加东西:

                int x1,y1,x2,y2,w;
                cin>>x1>>y1>>x2>>y2>>w;
                update(c1,x1,y1,w),update(c1,x1,y2+1,-w);
                update(c1,x2+1,y1,-w),update(c1,x2+1,y2+1,w);
            
                update(c2,x1,y1,w*x1),update(c2,x2+1,y1,-w*(x2+1));
                update(c2,x1,y2+1,-w*x1),update(c2,x2+1,y2+1,w*(x2+1));
            
                update(c3,x1,y1,w*y1),update(c3,x2+1,y1,-w*y1);
                update(c3,x1,y2+1,-w*(y2+1)),update(c3,x2+1,y2+1,w*(y2+1));
            
                update(c4,x1,y1,w*x1*y1),update(c4,x2+1,y1,-w*(x2+1)*y1);
                update(c4,x1,y2+1,-w*x1*(y2+1)),update(c4,x2+1,y2+1,w*(x2+1)*(y2+1));

    可以看到修改操作已经非常复杂了,然后是查询,其实查询更复杂,所以为了方便写一个get函数:

    int get(int x,int y)
    {
        return sum(c1,x,y)*(x+1)*(y+1)-sum(c2,x,y)*(y+1)-(x+1)*sum(c3,x,y)+sum(c4,x,y);
    }

    然后就可以正常查询了:

                int x1,y1,x2,y2;
                cin>>x1>>y1>>x2>>y2;
                cout<<get(x2,y2)-get(x2,y1-1)-get(x1-1,y2)+get(x1-1,y1-1)<<endl;

    在这里是没有读入原始数据的,针对原始数据,我们有两种方案,第一种方案是预处理出来一个前缀和,在查询的时候把二维前缀和的结果也加进去

    第二种方式是直接调用update函数把原始数据作为delta的一部分,其实对于复杂的情况来说,直接update就好了

    下面给出运用二维树状数组修改区间和查询区间的板子:

     1 #include<iostream>
     2 using namespace std;
     3 const int maxn=1005;
     4 const int maxm=1005;
     5 int n,m;
     6 int q;
     7 int a[maxn][maxm];
     8 int c1[maxn][maxm];
     9 int c2[maxn][maxm];
    10 int c3[maxn][maxm];
    11 int c4[maxn][maxm];
    12 int lowbit(int x)
    13 {
    14     return x&(-x);
    15 }
    16 void update(int c[][maxm],int x,int y,int z)
    17 {
    18     for(int i=x;i<=n;i+=lowbit(i))
    19     for(int j=y;j<=m;j+=lowbit(j))
    20         c[i][j]+=z;
    21 }
    22 
    23 int sum(int c[][maxm],int x,int y)
    24 {
    25     int ret=0;
    26     for(int i=x;i>=1;i-=lowbit(i))
    27     for(int j=y;j>=1;j-=lowbit(j))
    28         ret+=c[i][j];
    29     return ret;
    30 }
    31 
    32 int get(int x,int y)
    33 {
    34     return sum(c1,x,y)*(x+1)*(y+1)-sum(c2,x,y)*(y+1)-(x+1)*sum(c3,x,y)+sum(c4,x,y);
    35 }
    36 int main()
    37 {
    38     cin>>n>>m;
    39     cin>>q;
    40     while(q--)
    41     {
    42         int x;
    43         cin>>x;
    44         if(x==1)
    45         {
    46             int x1,y1,x2,y2,w;
    47             cin>>x1>>y1>>x2>>y2>>w;
    48             update(c1,x1,y1,w),update(c1,x1,y2+1,-w);
    49             update(c1,x2+1,y1,-w),update(c1,x2+1,y2+1,w);
    50         
    51             update(c2,x1,y1,w*x1),update(c2,x2+1,y1,-w*(x2+1));
    52             update(c2,x1,y2+1,-w*x1),update(c2,x2+1,y2+1,w*(x2+1));
    53         
    54             update(c3,x1,y1,w*y1),update(c3,x2+1,y1,-w*y1);
    55             update(c3,x1,y2+1,-w*(y2+1)),update(c3,x2+1,y2+1,w*(y2+1));
    56         
    57             update(c4,x1,y1,w*x1*y1),update(c4,x2+1,y1,-w*(x2+1)*y1);
    58             update(c4,x1,y2+1,-w*x1*(y2+1)),update(c4,x2+1,y2+1,w*(x2+1)*(y2+1));
    59         }
    60         if(x==2)
    61         {
    62             int x1,y1,x2,y2;
    63             cin>>x1>>y1>>x2>>y2;
    64             cout<<get(x2,y2)-get(x2,y1-1)-get(x1-1,y2)+get(x1-1,y1-1)<<endl;
    65         }
    66     }
    67     return 0;
    68 }

    在BZOJ3132中使用二维线段树或者是树套树是过不了的,可以看到这种方法还是十分优越的

    但是一定要注意数据范围还有空间够不够,否则直接JJ

    我们最后介绍三维树状数组:

    怎么拓展呢?直接在二维树状数组的基础上加一维就可以了,不用进行任何改动,这里我们只介绍其中的一种变式,那就是三维树状数组修改区间查询点

    (如果有人出三维树状数组修改区间查询区间的那种题,直接在二维树状数组修改区间查询区间的基础上改,应该不会有这种题的)

    下面给出代码,着重观察修改部分就可以了。

     1 #include<iostream>
     2 using namespace std;
     3 const int maxn=105;
     4 const int maxm=105;
     5 const int maxl=105;
     6 int n,m,l;
     7 int q;
     8 int a[maxn][maxm][maxl];
     9 int c[maxn][maxm][maxl];
    10 int lowbit(int x)
    11 {
    12     return x&(-x);
    13 }
    14 void update(int x,int y,int z,int w)
    15 {
    16     for(int i=x;i<=n;i+=lowbit(i))
    17     for(int j=y;j<=m;j+=lowbit(j))
    18     for(int k=z;k<=l;k+=lowbit(k))
    19         c[i][j][k]+=w;
    20 }
    21 
    22 int sum(int x,int y,int z)
    23 {
    24     int ret=0;
    25     for(int i=x;i>=1;i-=lowbit(i))
    26     for(int j=y;j>=1;j-=lowbit(j))
    27     for(int k=z;k>=1;k-=lowbit(k))
    28         ret+=c[i][j][k];
    29     return ret;
    30 }
    31 int main()
    32 {
    33     cin>>n>>m>>l;
    34     cin>>q;
    35     while(q--)
    36     {
    37         int x;
    38         cin>>x;
    39         if(x==1)
    40         {
    41             int x1,y1,z1,x2,y2,z2,w;
    42             cin>>x1>>y1>>z1>>x2>>y2>>z2>>w;
    43              update(x1,y1,z1,w); 
    44              update(x1,y2+1,z1,-w); 
    45              update(x2+1,y1,z1,-w); 
    46              update(x2+1,y2+1,z1,w); 
    47 
    48              update(x1,y1,z2+1,-w); 
    49              update(x1,y2+1,z2+1,w); 
    50              update(x2+1,y1,z2+1,w); 
    51              update(x2+1,y2+1,z2+1,-w); 
    52         }
    53         if(x==2)
    54         {
    55             int x,y,z;
    56             cin>>x>>y>>z;
    57             cout<<sum(x,y,z)<<endl;
    58         }
    59     }
    60     return 0;
    61 }

    目测没有三维修改查询区间的变态题的

    转载于:https://www.cnblogs.com/aininot260/p/9336527.html

    展开全文
  • 一,二维树状数组之单点修改矩阵查询 我们坐标轴也有一维二维,就是在线得基础上扩展到平面 我们的树状数组也是一样的道理,一维的时候我们存的是一个区间的和 二维就是存的一个矩阵 ... ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,399
精华内容 10,959
关键字:

二维树状数组