---
tags: codebook
---

# 2d segment tree

**CSES - Forest Queries II**

constexpr int maxn=1e3+5;
int arr[(maxn+1)<<2][(maxn+1)<<2];

#define xm ((xl+xr)>>1)
#define ym ((yl+yr)>>1)
void _build(auto& v,int xi,int xl,int xr,int yi=1,int yl=0,int yr=maxn){
	if(yr-yl==1){
		if(xr-xl==1){
			if(xl<int(v.size())&&yl<int(v.size())) 
				arr[xi][yi]=v[xl][yl];
		}else
			arr[xi][yi]=arr[xi<<1][yi]+arr[xi<<1|1][yi];
		return;
	}
	_build(v,xi,xl,xr,yi<<1,yl,ym),_build(v,xi,xl,xr,yi<<1|1,ym,yr);
	arr[xi][yi]=arr[xi][yi<<1]+arr[xi][yi<<1|1];
}
void build(auto& v,int xi=1,int xl=0,int xr=maxn){
	if(xr-xl>1)
		build(v,xi<<1,xl,xm),build(v,xi<<1|1,xm,xr);
	_build(v,xi,xl,xr);
}
int _query(int yql,int yqr,int xi,int yi=1,int yl=0,int yr=maxn){
	if(yqr<=yl||yr<=yql) return 0;
	// debug(yl,yr);
	if(yql<=yl&&yr<=yqr) return arr[xi][yi];
	return _query(yql,yqr,xi,yi<<1,yl,ym)+_query(yql,yqr,xi,yi<<1|1,ym,yr);
}
int query(int xql,int xqr,int yql,int yqr,int xi=1,int xl=0,int xr=maxn){
	if(xqr<=xl||xr<=xql) return 0;
	// debug(xl,xr);
	if(xql<=xl&&xr<=xqr) return _query(yql,yqr,xi);
	return query(xql,xqr,yql,yqr,xi<<1,xl,xm)+query(xql,xqr,yql,yqr,xi<<1|1,xm,xr);
}
void _update(int yp,int xi,int xl,int xr,int yi=1,int yl=0,int yr=maxn){
	if(yp<yl||yr<=yp) return;
	if(yr-yl==1){
		if(xr-xl==1)
			arr[xi][yi]^=1;
		else
			arr[xi][yi]=arr[xi<<1][yi]+arr[xi<<1|1][yi];
		return;
	}
	_update(yp,xi,xl,xr,yi<<1,yl,ym),_update(yp,xi,xl,xr,yi<<1|1,ym,yr);
	arr[xi][yi]=arr[xi][yi<<1]+arr[xi][yi<<1|1];
}
void update(int xp,int yp,int xi=1,int xl=0,int xr=maxn){
	if(xp<xl||xr<=xp) return;
	if(xr-xl>1)
		update(xp,yp,xi<<1,xl,xm),update(xp,yp,xi<<1|1,xm,xr);
	_update(yp,xi,xl,xr);
}
void _print(auto& v,int xl,int xi,int yi=1,int yl=0,int yr=maxn){
	if(yr-yl==1){if(yl<int(v.size())) debug(xl,yl,arr[xi][yi]);return;}
	_print(v,xl,xi,yi<<1,yl,ym),_print(v,xl,xi,yi<<1|1,ym,yr);
}
void print(auto& v,int xi=1,int xl=0,int xr=maxn){
	if(xr-xl>1)
		print(v,xi<<1,xl,xm),print(v,xi<<1|1,xm,xr);
	else
		if(xl<int(v.size())) _print(v,xl,xi);
}
#undef xm
#undef ym

inline void solve() {
	int n,m; cin>>n>>m;
	V<V<int>> v(n,V<int>(n));
	for(int i=0;i<n;i++){
		string str;cin>>str;
		for(int j=0;j<n;j++)
			v[i][j]=(str[j]=='*');
	}
	build(v);
	// cerr<<query(0,n,0,n)<<endl;
	// cerr<<"poop"<<endl;
	while(m--){
		int op,x1,x2,y1,y2; cin>>op;
		switch(op){
		case 1:
			cin>>x1>>y1,x1--,y1--;
			update(x1,y1);
			break;
		case 2:
			cin>>x1>>y1>>x2>>y2,x1--,y1--;
			cout<<query(x1,x2,y1,y2)<<endl;
			break;
		}
	}
}