//POJ 1195 Mobile phones 线段树 二维线段树 单点更新 区间求和
/*
题意:
一个矩阵,初始化为0,两种操作:
1、将某点增加val
2、查询一个子矩阵的和
思路:
二维线段树,单点更新,区间求和,记得pushup.
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 1050
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int sum[N*3][N*3];
int n;
void SubBuild(int rt,int l,int r,int t){
sum[t][rt] = 0;
if(l!=r){
int mid = (l + r) >> 1;
SubBuild(lson,t);
SubBuild(rson,t);
}
}
void Build(int rt,int l,int r){
SubBuild(1,1,n,rt);
if(l!=r){
int mid = (l + r) >> 1;
Build(lson);
Build(rson);
}
}
void SubUpdate(int rt,int l,int r,int y,int val,int t){
if(l == r)
sum[t][rt] += val;
else{
int mid = (l + r) >> 1;
if(y <= mid) SubUpdate(lson,y,val,t);
else SubUpdate(rson,y,val,t);
sum[t][rt] = sum[t][rt<<1] + sum[t][rt<<1|1];
}
}
void Update(int rt,int l,int r,int x,int y,int val){
SubUpdate(1,1,n,y,val,rt);
if(l!=r){
int mid = (l + r) >> 1;
if(x <= mid) Update(lson,x,y,val);
else Update(rson,x,y,val);
}
}
__int64 SubQuery(int rt,int l,int r,int LY,int RY,int t){
if(LY <= l && RY >= r)
return sum[t][rt];
int mid = (l + r) >> 1;
__int64 ans = 0;
if(LY <= mid) ans += SubQuery(lson,LY,RY,t);
if(RY > mid ) ans += SubQuery(rson,LY,RY,t);
return ans;
}
__int64 Query(int rt,int l,int r,int LX,int RX,int LY,int RY){
if(LX <= l && RX >= r){
return SubQuery(1,1,n,LY,RY,rt);
}
int mid = (l + r) >> 1;
__int64 ans = 0;
if(LX <= mid) ans += Query(lson,LX,RX,LY,RY);
if(RX > mid ) ans += Query(rson,LX,RX,LY,RY);
return ans;
}
int main(){
int op;
int a,b,c,d;
while(scanf("%d %d",&op,&n)!=EOF){
++n;
Build(1,1,n);
while(scanf("%d",&op)){
if(op == 3)
break;
if(op == 1){
scanf("%d %d %d",&a,&b,&c);
++a,++b;
Update(1,1,n,a,b,c);
}
else{
scanf("%d %d %d %d",&a,&b,&c,&d);
++a,++b,++c,++d;
printf("%I64d\n",Query(1,1,n,a,c,b,d));
}
}
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1746750
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1740501
POJ题解 个人写法 线段树每个人都不一样
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2763 程序 线段树 LCA 2000MS AC
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1747400
NULL 博文链接:https://128kj.iteye.com/blog/1705139
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ3468,线段树处理,注意longlongint
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
poj分类poj分类poj分类poj分类
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论