POJ 2029 二维树状数组

浅浅的花香味﹌ 2022-11-20 11:54 201阅读 0赞

二维树状数组模板题

### AC代码 ###

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    const int max_N=500+1;
    
    int bit[max_N][max_N];
    int n,m;
    
    int lowbit(int x)
    {
        
        return x&(-x);
    }
    
    void update(int x,int y,int val)
    {
        
        for(int i=x;i<=n;i+=lowbit(i))
        {
        
            for(int j=y;j<=m;j+=lowbit(j))
            {
        
                bit[i][j]+=val;
            }
        }
    }
    
    int sum(int x,int y)
    {
        
        int ret=0;
        for(int i=x;i>0;i-=lowbit(i))
        {
        
            for(int j=y;j>0;j-=lowbit(j))
            {
        
                ret+=bit[i][j];
            }
        }
        return ret;
    }
    
    int main()
    {
        
        int N;
        while(scanf("%d",&N) && N)
        {
        
            memset(bit,0,sizeof(bit));
            scanf("%d%d",&n,&m);
            // 建立二维树状数组bit
            int x,y;
            for(int i=0;i<N;++i)
            {
        
                scanf("%d %d",&x,&y);
                update(x,y,1);
            }
            int S,T;
            scanf("%d%d",&S,&T);
            int ans=-1;
            for(int i=1;i<=n-S+1;++i)
            {
        
                for(int j=1;j<=m-T+1;++j)
                {
        
                    int x1,x2,y1,y2;
                    x1=i;
                    y1=j;
                    x2=i+S-1;
                    y2=j+T-1;
                    int now=sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
                    //cout<<"??"<<endl;
                    ans=max(ans,now);
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }