二维线段树
把线段树转移到二维还是用的一维时的思想。
一维的时候父区间分为两个子区间，
那么二维的时候是不是也可以把父矩阵分为四个子矩阵呢？
应该是可以的。
那么仿照一维的写法：
  build(k*4+1,lx,ly,xmid,ymid);
  build(k*4+2,xmid+1,ly,rx,ymid);
  build(k*4+3,lx,ymid+1,xmid,ry);
  build(k*4+4,xmid+1,ymid+1,rx,ry);

 if (lx<=g[k].xmid)and(ly<=g[k].ymid) then insert(k*4+1,lx,ly,rx,ry,coo);
 if (rx>g[k].xmid)and(ly<=g[k].ymid) then insert(k*4+2,lx,ly,rx,ry,coo);
 If (lx<=g[k].xmid)and(ry>g[k].ymid) then insert(k*4+3,lx,ly,rx,ry,coo);
 if (rx>g[k].xmid)and(ry>g[k].ymid) then insert(k*4+4,lx,ly,rx,ry,coo);

那么差不多是可行的。
可是会出现一种特殊情况，即大小为1×2的矩形
它不是单个的子矩阵，也不是有四个孩子的父矩阵。它比较异类。
所以建树的时候我加了一句特判（不然216）：
if (lx<>rx)or(ly<>ry) then build(k*4+1,lx,ly,xmid,ymid);
if lx<>rx then build(k*4+2,xmid+1,ly,rx,ymid);
if ly<>ry then build(k*4+3,lx,ymid+1,xmid,ry);
if (lx<>rx)and(ly<>ry) then build(k*4+4,xmid+1,ymid+1,rx,ry);
然后pku1656这题的样例就轻松过掉了。
可是去网上测总是Runtime Error
把Discuss上的那段C++的二维线段树看了又看也查不出错。
调了一个下午后 开始自己生成随机数据写。
果真是216了。   发生在insert操作里。
原因是在insert是产生了非法节点，即大小为1×2的矩形的非法孩子。
比如
（84,58）
（85,58）
这个矩形是当前搜到的矩形。而它的下半部分在插入范围之内，上半部分不在，那么我们就需要找它的子区间，这个时候如果不判断又会去找它右下角的孩子，但实际上它只在左上角和左下角有孩子，那么进入非法的孩子区间之后，就会看到216.

想来想去没有什么好办法，就写了一个暴力的判断该区间是否为合法区间的v[]布尔数组。
这样所有操作再添上判断是否合法就可以AC了。
至于楼主的那段C++代码的神奇之处有三点
它不建树预处理  2.插入和求和操作时一并计算当前区间各点坐标。可节省空间。
综合上面两点神奇之处就可以得到第三点神奇之处，即使遇到非法区间也能全身而退。
最多进入非法状态一层就可以在正常的判断下退出过程。有兴趣的可以模拟下。



下面是我的代码（P写的，加暴力判断，比较丑）：
type gtree=record
      lx,ly,xmid,rx,ry,ymid,coo,sum:longint;
     end;

var g:array[0..30000] of gtree;
    v:array[0..30000] of boolean;
    i,question,lx,ly,L:longint;
    x:char;

procedure build(k,lx,ly,rx,ry:longint);
begin
  g[k].lx:=lx; g[k].ly:=ly; g[k].rx:=rx; g[k].ry:=ry;
  g[k].xmid:=(lx+rx) div 2; g[k].ymid:=(ly+ry) div 2;
  g[k].coo:=0; g[k].sum:=0; v[k]:=true;
  with g[k] do
    begin
     if (lx<>rx)or(ly<>ry) then build(k*4+1,lx,ly,xmid,ymid);
     if lx<>rx then build(k*4+2,xmid+1,ly,rx,ymid);
     if ly<>ry then build(k*4+3,lx,ymid+1,xmid,ry);
     if (lx<>rx)and(ly<>ry) then build(k*4+4,xmid+1,ymid+1,rx,ry);
    end;
end;

procedure push(k:longint);
begin
   if g[k].coo=-1 then exit;
   if v[k*4+1] then begin
                  g[k*4+1].coo:=g[k].coo;
                  g[k*4+1].sum:=(g[k*4+1].rx-g[k*4+1].lx+1)*(g[k*4+1].ry-g[k*4+1].ly+1)*g[k].coo;
                end;
   if v[k*4+2] then begin
                  g[k*4+2].coo:=g[k].coo;
                  g[k*4+2].sum:=(g[k*4+2].rx-g[k*4+2].lx+1)*(g[k*4+2].ry-g[k*4+2].ly+1)*g[k].coo;
                 end;
   if v[k*4+3] then begin
                  g[k*4+3].coo:=g[k].coo;
                  g[k*4+3].sum:=(g[k*4+3].rx-g[k*4+3].lx+1)*(g[k*4+3].ry-g[k*4+3].ly+1)*g[k].coo;
                 end;
   if v[k*4+4] then begin
                  g[k*4+4].coo:=g[k].coo;
                  g[k*4+4].sum:=(g[k*4+4].rx-g[k*4+4].lx+1)*(g[k*4+4].ry-g[k*4+4].ly+1)*g[k].coo;
                 end;
   g[k].coo:=-1;
end;

procedure update(k:longint);
begin
   g[k].sum:=0;
   if v[k*4+1] then inc(g[k].sum,g[k*4+1].sum);
   if v[k*4+2] then inc(g[k].sum,g[k*4+2].sum);
   if v[k*4+3] then inc(g[k].sum,g[k*4+3].sum);
   if v[k*4+4] then inc(g[k].sum,g[k*4+4].sum);
end;

procedure insert(k,lx,ly,rx,ry,coo:longint);
begin
   if (lx<=g[k].lx)and(g[k].rx<=rx)and(ly<=g[k].ly)and(g[k].ry<=ry)
   then begin
          g[k].coo:=coo;
          g[k].sum:=(g[k].rx-g[k].lx+1)*(g[k].ry-g[k].ly+1)*g[k].coo;
        end
   else begin
          push(k);
          if (v[k*4+1])and(lx<=g[k].xmid)and(ly<=g[k].ymid) then insert(k*4+1,lx,ly,rx,ry,coo);
          if (v[k*4+2])and(rx>g[k].xmid)and(ly<=g[k].ymid) then insert(k*4+2,lx,ly,rx,ry,coo);
          if (v[k*4+3])and(lx<=g[k].xmid)and(ry>g[k].ymid) then insert(k*4+3,lx,ly,rx,ry,coo);
          if (v[k*4+4])and(rx>g[k].xmid)and(ry>g[k].ymid) then insert(k*4+4,lx,ly,rx,ry,coo);
          update(k);
        end;
end;

function getsum(k,lx,ly,rx,ry:longint):longint;
begin
   getsum:=0;
   if (lx<=g[k].lx)and(g[k].rx<=rx)and(ly<=g[k].ly)and(g[k].ry<=ry)
   then inc(getsum,g[k].sum)
   else begin
         push(k);
         if (v[k*4+1])and(lx<=g[k].xmid)and(ly<=g[k].ymid) then inc(getsum,getsum(k*4+1,lx,ly,rx,ry));
         if (v[k*4+2])and(rx>g[k].xmid)and(ly<=g[k].ymid) then inc(getsum,getsum(k*4+2,lx,ly,rx,ry));
         if (v[k*4+3])and(lx<=g[k].xmid)and(ry>g[k].ymid) then inc(getsum,getsum(k*4+3,lx,ly,rx,ry));
         if (v[k*4+4])and(rx>g[k].xmid)and(ry>g[k].ymid) then inc(getsum,getsum(k*4+4,lx,ly,rx,ry));
        end;
end;

begin
   fillchar(v,sizeof(v),false);
   build(0,1,1,101,101);
   readln(question);
   for i:=1 to question do
   begin
     read(x);
     case x of
      'B':begin
           read(x);read(x);read(x);read(x);
           readln(lx,ly,L);
           insert(0,lx,ly,lx+L-1,ly+L-1,1);
          end;
      'W':begin
           read(x);read(x);read(x);read(x);
           readln(lx,ly,L);
           insert(0,lx,ly,lx+L-1,ly+L-1,0);
          end;
      'T':begin
           read(x);read(x);read(x);
           readln(lx,ly,L);
           writeln(getsum(0,lx,ly,lx+L-1,ly+L-1));
          end;
     end;
  end;
end.