POJ 1195 Mobile phones

树状数组第一题，上来就是二维树状数组，这是逼着我用树状数组做啊，二维线段树不会写啊~~

题目大意：

给定矩阵大小，可以更新矩阵中的某些数，要求输出某个范围内的所有数之和。

解题思路：

二维树状数组可解。

一维树状数组讲解：点击打开。

二维树状数组只是在更新方式上稍作改变。

在数组长度为n的树状数组中：

寻找下一个需要添加的数的下标：

int lowbit(int x)
{
    return x&(-x);
}

一维树状数组更新是这样的：

void add(int x,int val)
{
    for(;x<=n;x+=lowbit(x))
    {
        num[x]+=val;
    }
}

void  add(int x,int y,int val)
{
    for(int i=x;i<=s;i+=lowbit(i))
    {
        for(int j=y;j<=s;j+=lowbit(j))
        {
            num[i][j]+=val;
        }
    }
}

一维树状数组查询是这样的：

int query(int x)
{
    int ans=0;
    for(;x>0;x-=lowbit(x))
    {
        ans+=c[i];
    }
    return ans;
}

查询的是1到x的数总和。

int query(int x,int y)
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        for(int j=y;j>0;j-=lowbit(j))
        {
            ans+=num[i][j];
        }
    }
    return ans;
}

下面是代码：

#include <stdio.h>
#include <string.h>
int num[1050][1050],s;
int lowbit(int x)
{
    return x&(-x);
}
void  add(int x,int y,int val)
{
    for(int i=x;i<=s;i+=lowbit(i))
    {
        for(int j=y;j<=s;j+=lowbit(j))
        {
            num[i][j]+=val;
        }
    }
}
int query(int x,int y)
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        for(int j=y;j>0;j-=lowbit(j))
        {
            ans+=num[i][j];
        }
    }
    return ans;
}
int main()
{
    int t,q,x,y,sum,l,r,a;
    scanf("%d%d",&t,&s);
    memset(num,0,sizeof(num));
    while(scanf("%d",&q),q<3)
    {
        if(q==1)
        {
            scanf("%d%d%d",&x,&y,&a);
            x++;
            y++;
            add(x,y,a);
        }
        else if(q==2)
        {
            scanf("%d%d%d%d",&x,&y,&l,&r);
            x++;
            y++;
            l++;
            r++;
            printf("%d\n",query(l,r)-query(l,y-1)-query(x-1,r)+query(x-1,y-1));
        }
    }
    return 0;
}

POJ 1195 Mobile phones,布布扣,bubuko.com

POJ 1195 Mobile phones

原文：http://blog.csdn.net/lin375691011/article/details/21247409