-
Notifications
You must be signed in to change notification settings - Fork 5
/
2d segment tree.cpp
82 lines (73 loc) · 2.22 KB
/
2d segment tree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<vector>
using namespace std;
typedef int value_type;
vector<value_type> tree;
bool inRange(size_t qx1,size_t qx2,size_t qy1,size_t qy2,size_t nx1,size_t nx2,size_t ny1,size_t ny2)
{
if(nx2<nx1||ny2<ny1) // node is invalid.
return false;
if(qx2<nx1||qx1>nx2) // x is out of bounds
return false;
if(qy2<ny1||qy1>ny2) // y is out of bounds
return false;
return true;
}
inline size_t child(size_t node,size_t number)
{
return node*4+number;
}
void update(size_t qx1,size_t qx2,size_t qy1,size_t qy2,size_t nx1,size_t nx2,size_t ny1,size_t ny2, size_t node, value_type &value)
{
if(!inRange(qx1,qx2,qy1,qy2,nx1,nx2,ny1,ny2))
return;
else if(nx1>=qx1&&nx2<=qx2&&ny1>=qy1&&ny2<=qy2&&nx1==nx2&&ny1==ny2) // node is within query
tree[node]+=value;
else
{
update(qx1,qx2,qy1,qy2, nx1,(nx1+nx2)/2,ny1,(ny2+ny1)/2, child(node,1), value);
update(qx1,qx2,qy1,qy2, nx1, (nx1+nx2)/2, (ny1+ny2)/2+1, ny2, child(node,2), value);
update(qx1,qx2,qy1,qy2, (nx1+nx2)/2+1, nx2, ny1, (ny2+ny1)/2, child(node,3), value);
update(qx1,qx2,qy1,qy2, (nx1+nx2)/2+1, nx2, (ny1+ny2)/2+1, ny2, child(node,4), value);
tree[node]=tree[child(node,1)]+tree[child(node,2)]+tree[child(node,3)]+tree[child(node,4)];
}
}
value_type query (size_t qx1,size_t qx2,size_t qy1,size_t qy2,size_t nx1,size_t nx2,size_t ny1,size_t ny2,size_t node)
{
if(!inRange(qx1,qx2,qy1,qy2,nx1,nx2,ny1,ny2))
return 0;
else if(nx1>=qx1&&nx2<=qx2&&ny1>=qy1&&ny2<=qy2)
return tree[node];
else
{
value_type LL=query(qx1,qx2,qy1,qy2, nx1,(nx1+nx2)/2, ny1,(ny2+ny1)/2, child(node,1));
value_type LR=query(qx1,qx2,qy1,qy2, nx1, (nx1+nx2)/2, (ny1+ny2)/2+1, ny2, child(node,2));
value_type RL=query(qx1,qx2,qy1,qy2, (nx1+nx2)/2+1, nx2, ny1, (ny2+ny1)/2, child(node,3));
value_type RR=query(qx1,qx2,qy1,qy2, (nx1+nx2)/2+1, nx2, (ny1+ny2)/2+1, ny2, child(node,4));
return LL+LR+RL+RR;
}
}
int main()
{
freopen("test.txt","r",stdin);
int n;
cin>>n;
tree.resize(4*n*n);
int q;
cin>>q;
while(q--)
{
int type;
cin>>type;
int x1,x2,y1,y2;
cin>>x1>>x2>>y1>>y2;
if(type)
cout<<query(x1,x2,y1,y2,0,n-1,0,n-1,0)<<endl;
else
{
value_type value;
cin>>value;
update(x1,x2,y1,y2,0,n-1,0,n-1,0,value);
}
}
}