2D range add/fetch

ll fxy[MAN][MAN]; // coefficient of x*y at [r,c]
ll fx[MAN][MAN];  // coefficient of x   at [r,c]
ll fy[MAN][MAN];  // coefficient of y   at [r,c]
ll fc[MAN][MAN];  // additive           at [r,c]

// 2D fenwick tree insert
void insert(ll f[MAN][MAN],ll x,ll y,ll k){
  for (ll i=x; i<MAN; i|=i+1)
    for (ll j=y; j<MAN; j|=j+1)
      f[i][j]+=k;
}

// 2D fenwick tree lookup
ll get(ll f[MAN][MAN],ll x,ll y){
  ll res=0;
  for (ll i=x; i>=0; --(i&=i+1))
    for (ll j=y; j>=0; --(j&=j+1))
      res+=f[i][j];
  return res;
}

// evaluate functions at (x,y)
ll calc(ll x,ll y){
  return get(fxy, x, y)*x*y
       + get(fx,  x, y)*x
       + get(fy,  x, y)*y
       + get(fc,  x, y);
}

// create infinite rectangle with lower-left corner at (a,b)
ll add(ll x,ll y,ll k){
  // area(x,y) => (x+1-a)*(y+1-b)
  //           == x*y+x-b*x + y+1-b + -a*y-a+a*b
  //           == x*y + x*(1-b) + y*(1-a) + 1+a*b-a-b

  ll mxy = k;
  ll mx  = k*(1-y);
  ll my  = k*(1-x);
  ll mc  = k*(1+x*y-x-y);

  insert(fxy, x,y, mxy);
  insert(fx,  x,y, mx);
  insert(fy,  x,y, my);
  insert(fc,  x,y, mc);
}