二次元セグメント木

二次元のセグメント木。二次元配列上でセグ木的なことができる。

二次元累積和の代わりにこれを使うことでサボれる！うれしい！

code:cpp

void _main(){

LL(m,n,a,b);

SegmentTree2D seg(n,m,[](int a,int b){return a+b;},0);

SegmentTree2D seg2(n,m,[](int a,int b){return a+b;},0);

rep(i,n){

rep(j,m){

LL(x);

if(x==-1){

seg2.set(i,j,seg2.get(i,j)+1);

}

else{

seg.set(i,j,seg.get(i,j)+x);

}

}

}

seg.build();seg2.build();

int ans = 1<<30;

rep(i,n-b+1){

rep(j,m-a+1){

if(seg2.query(i,j,i+b,j+a)==0){

chmin(ans,seg.query(i,j,i+b,j+a));

}

}

}

O(ans);

}

TLEになっている