原创:jack35
注意:
- 可减信息都可以如此维护
- (二维情形)空间
O(n2)
,单次加/求和
O(log2n)
Code 矩阵加/矩阵求和
ll get(ll z,ll x,ll y)
{
ll ans=0;
for(ll i=x;i;i-=lowbit(i)) for(ll j=y;j;j-=lowbit(j)) ans+=t[z][i][j];
return ans;
}
ll sum(ll x,ll y)
{
return (((x+1)*(y+1)*get(0,x,y))%mo-((x+1)*get(2,x,y))%mo-((y+1)*get(1,x,y))%mo+get(3,x,y)+mo+mo)%mo;
}
void put(ll z,ll x,ll y,ll w)
{
for(ll i=x;i<=n;i+=lowbit(i)) for(ll j=y;j<=m;j+=lowbit(j)) t[z][i][j]+=w;
}
void ins(ll x,ll y,ll w)
{
put(0,x,y,w);
put(1,x,y,w*x);
put(2,x,y,w*y);
put(3,x,y,w*x*y);
}
void add(int x1,int y1,int x2,int y2,int z)
{
ins(x1,y1,z);ins(x1,y2+1,-z);ins(x2+1,y1,-z);ins(x2+1,y2+1,z);
}
void query(int x1,int y1,int x2,int y2)
{
return sum(x,y)-sum(x,y1-1)-sum(x1-1,y)+sum(x1-1,y1-1);
}