Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 二维数据结构 code如下

Posted by ACAccepted at 2019-10-04 11:29:25 on Problem 1195 and last updated at 2019-10-04 11:31:17
```/*
Auther:xzy
Time:782MS
status:Accepted
Submit ID:20923452
*/
//二维树状数组
#include <cstdio>
using namespace std;

template<typename T>
{
T x=0,f=1;char c=getchar();
while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return x*f;
}

const int MAXN=10005;
int n;

namespace flat_BIT
{
int tree[MAXN][MAXN];

inline void update(int x,int y,int val)
{
for (int i=x;i<=n;i+=(i&-i))
for (int j=y;j<=n;j+=(j&-j)) tree[i][j]+=val;
}

inline int query(int x,int y)
{
int sum=0;
for (int i=x;i>0;i-=(i&-i))
for (int j=y;j>0;j-=(j&-j)) sum+=tree[i][j];
return sum;
}

inline int query(int x1,int y1,int x2,int y2)
{
return query(x2,y2)-query(x2,y1-1)-query(x1-1,y2)+query(x1-1,y1-1);
}
}

int main()
{
{
if (cas==1)
{
flat_BIT::update(x+1,y+1,d);
}
else
{
printf("%d\n",flat_BIT::query(x+1,y+1,x0+1,y0+1));
}
}
return 0;
}

/*
Auther:xzy
Time:1422MS
status:Accepted
Submit ID:20923574
*/
//二维线段树
#include <cstdio>
using namespace std;

template<typename T>
{
T x=0,f=1;char c=getchar();
while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return x*f;
}

const int MAXN=2025;
int n;

namespace flat_stree
{
struct stree_y
{
int val[MAXN<<2];

inline void update(int k,int l,int r,int x,int d)
{
if (l==r) {val[k]+=d;return ;}
int mid=l+r>>1;
if (x<=mid) update(k<<1,l,mid,x,d);
else update(k<<1|1,mid+1,r,x,d);
val[k]=val[k<<1]+val[k<<1|1];
}

inline int query(int k,int l,int r,int _l,int _r)
{
if (_l<=l&&_r>=r) return val[k];
int mid=l+r>>1,res=0;
if (_l<=mid) res+=query(k<<1,l,mid,_l,_r);
if (_r>mid) res+=query(k<<1|1,mid+1,r,_l,_r);
return res;
}
};

struct stree_x
{
struct stree_y root[MAXN<<2];

inline void update(int k,int l,int r,int x,int y,int d)
{
root[k].update(1,1,n,y,d);
if (l==r) return ;
int mid=l+r>>1;
if (x<=mid) update(k<<1,l,mid,x,y,d);
else update(k<<1|1,mid+1,r,x,y,d);
}

inline int query(int k,int l,int r,int _l,int _r,int __l,int __r)
{
if (_l<=l&&_r>=r) return root[k].query(1,1,n,__l,__r);
int mid=l+r>>1,res=0;
if (_l<=mid) res+=query(k<<1,l,mid,_l,_r,__l,__r);
if (_r>mid) res+=query(k<<1|1,mid+1,r,_l,_r,__l,__r);
return res;
}
}root;
}

int main()
{
{
if (cas==1)
{
flat_stree::root.update(1,1,n,x+1,y+1,d);
}
else
{
printf("%d\n",flat_stree::root.query(1,1,n,x+1,x0+1,y+1,y0+1));
}
}
return 0;
}```

Followed by: