poj1195(二维树状数组)

poj1195(二维树状数组)

题目链接:https://vjudge.net/problem/POJ-1195

题意:有s*s的矩阵,初始化为全0,有两种操作,单点修改(x,y)的值,区间查询(x,y)的值(l<=x<=r,b<=y<=t)。

思路:二维树状数组裸应用查询区间(l,b)~(r,t)的值可转换为tr[r][t]-tr[l-1][t]-tr[r][b-1]+tr[l-1][b-1]。要注意的是输入的x,y是从0开始的,所以要加1。

AC代码:  

#include<cstdio>
#include<cctype>
using namespace std;

inline int read(){
    int x=0,f=0;char c=0;
    while(!isdigit(c)){f|=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return f?-x:x;
}

int op,s,tr[1030][1030];

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

void update(int x,int y,int k){
    while(x<=s){
        int tmp=y;
        while(tmp<=s){
            tr[x][tmp]+=k;
            tmp+=lowbit(tmp);
        }
        x+=lowbit(x);
    }
}

int query(int x,int y){
    int ans=0;
    while(x>0){
        int tmp=y;
        while(tmp>0){
            ans+=tr[x][tmp];
            tmp-=lowbit(tmp);
        }
        x-=lowbit(x);
    }
    return ans;
}

int main(){
    op=read(),s=read();
    while(op=read(),op!=3){
        if(op==1){
            int x=read()+1,y=read()+1,k=read();
            update(x,y,k);
        }
        else{
            int l=read()+1,b=read()+1,r=read()+1,t=read()+1;
            printf("%d\n",query(r,t)-query(l-1,t)-query(r,b-1)+query(l-1,b-1));
        }
    }
    return 0;
}

 

转载于:https://www.cnblogs.com/FrankChen831X/p/10799465.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/100945.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 启动redis出现Creating Server TCP listening socket *:6379: bind: No such file or directory

    启动redis出现Creating Server TCP listening socket *:6379: bind: No such file or directory[6644]02Apr23:11:58.976#CreatingServerTCPlisteningsocket*:6379:bind:Nosuchfileordirectoryredis报错:[6644]02Apr23:11:58.976#CreatingServerTCPlisteningsocket*:6379:bind:

  • pytorch安装-国内镜像源

    pytorch安装-国内镜像源在安装好cuda和cudnn之后安装pytorch的方法网上很多的方法都不是镜像下载,或者镜像下载因为系统的问题找不到库打开官网,找到对应合适的版本(cuda):https://pytorch.org/get-started/locally/之后复制下面这一行指令:condainstallpytorchtorchvisiontorchaudiocudatoolkit=11.0-cpytorch接下来就是关键一步了,把-cpytorch表示的pytorch源,更改为国内的镜像。

  • 无线通信架构_无线接入网的三层架构

    无线通信架构_无线接入网的三层架构无线通信主要是利用无线电(Radio)射频(RF)技术的通信方式,无线网络是采用无线通信技术实现的网络。无线通信知识架构参考这篇文章——https://blog.csdn.net/zh328271057/article/details/85040145问题在于,无线通信在网络技术方面主要包含无线网络和移动网络(或称为蜂窝移动网络)无线网络可分为两种:近距离无线网络和远距离无线网络,近距离…

  • 数据结构PDF下载

    数据结构PDF下载数据结构算法实现及解析C语言[第二版]高一凡pdf文字版http://qunying.jb51.net:81/201303/books/sjjg_sfszjjx_jb51net.rar大话数据结构中文PDF清晰扫描版完整版[36M]http://qunying.jb51.net:81/201209/books/dhsjjg_jb51.rarC#语言描述数据结构pdf版ht…

  • eclipse配置android开发环境_eclipse android开发环境搭建

    eclipse配置android开发环境_eclipse android开发环境搭建一、.安装JDK,不再赘述二、安装eclipse,不再赘述三、安装SDK,也就是安卓开发库1.下载并安装AndroidSDK首先,下载AndroidSDKTools,翻过墙的朋友可以去GoogleAndroid的官网上下载(http://developer.android.com/sdk/index.html)。不愿意翻墙的朋友,可以去我的bd网盘上下载(http://pan.baidu.com/s/1nt8BcBB),或者去这个网站下载(http://www.androiddevtools.

  • 谷歌浏览器中kindeditor编译器字体不能为微软雅黑的问题?

    谷歌浏览器中kindeditor编译器字体不能为微软雅黑的问题?

    2021年10月22日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号