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)


相关推荐

  • 协程概述

    协程概述协程不是进程,也不是线程,它就是一个函数,一个特殊的函数——可以在某个地方挂起,并且可以重新在挂起处继续运行。所以说,协程与进程、线程相比,不是一个维度的概念。一个进程可以包含多个线程,一个线程也可以包含多个协程,也就是说,一个线程内可以有多个那样的特殊函数在运行。但是有一点,必须明确,一个线程内的多个协程的运行是串行的。如果有多核CPU的话,多个进程或一个进程内的多个线程是可以并行运行的,但是一…

  • http_build_query()函数使用方法

    http_build_query()函数使用方法

  • 最短路径之Dijkstra(迪杰斯特拉)算法(无向图)

    最短路径之Dijkstra(迪杰斯特拉)算法(无向图)简介Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。由for循环可知,其时间复杂度是O(n^2)。原理在已知图的邻接矩阵net.vexs[i][j](无向网,含权值的图)的条件下,通过遍历已知图的所有路径,用dis[i]数组来记录到i点…

  • Git权威指南学习笔记(二)Git暂存区[通俗易懂]

    Git权威指南学习笔记(二)Git暂存区

  • tiktok案例分析_metaobject

    tiktok案例分析_metaobjecttictoc12.ned文件//input:指定当前门是输入门,只能和输出门连接,只能接受消息//output:当前门是输出门,只能和输入门连接,只能发送消息//inout:既是输入门又是输出门,既能发送消息也能接受消息simpleTxc12{parameters:@display(“i=block/routing”);gates:inoutgate[];//declaretwowayconnections声明双向连接}

  • idea 创建properties配置文件

    idea 创建properties配置文件我们在j2ee当中,连接数据库的时候经常会用到properties配置文件,我们原来在eclipse或者myeclipse当中会在src文件夹目录下创建一个properties文件。然后用如下代码去加载配置文件InputStreamin=PropertiesDemo.class.getClassLoader().getResourceAsStream(“database.properti

    2022年10月29日

发表回复

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

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