题目链接：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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/100945.html原文链接：https://javaforall.net
