//FAFU 1100 线段树 二维线段树 单点更新 区间求和 /* 题意: 一个矩阵,初始化为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; }