线段树

线段树是二叉搜索树的一种。与一般的二叉搜索树不同的是，线段树保存的是所有元素可能取的值，而不是每个元素。通常情况下，线段树只用叶节点表示每个值。而其余的节点对应的就是一个范围。

由于线段树所保存的节点是固定的，所以可以直接在开始的时候做成一个比较完美的二叉树，而不需要自平衡的操作。对于比较小的数据，这个二叉树通常能像完全二叉树一样，直接保存在一维数组中。 （注：其实假如二叉堆形式存不下线段树，链表式也是存不下的。可以证明大小为L的区间节点编号最大为2*L-1）

一般情况下，线段树的结点类型定义如下：

 type linetree = ^rec
      rec=record             
      i,j:integer;           {区间端点}
      count:integer;         {覆盖的区间数}
      lchild,rchild:linetree;{子节点}
      end;

线段树是一个小作品，欢迎帮助扩充这个条目。

Program PIT_Sample;
Uses Math;
Type Ptype=^node;
      Node=record
 		s,k   :	  longint;   //sum,key
 		l,r   :	  ptype;     //left,right
 		end;
Var b,e,i,n,k                   :      longint;
    PIT                         :      Ptype;
    c				:      char;
 
Procedure Build(var q:Ptype);
begin
    q^.s:=0; q^.k:=0; q^.l:=nil; q^.r:=nil;
end;
 
Procedure Ins(t:Ptype; b,e,k:longint);
var q:ptype;
begin
    if b=e then if t^.k<>k then begin t^.k:=k; t^.s:=0; end 
    else 
      else if k<=(b+e) shr 1 then
        begin
          if t^.l=nil then begin new(q); build(q); t^.l:=q; end;
          Ins(t^.l,b,(b+e) shr 1,k);
        end 
      else
        begin
          if t^.r=nil then begin new(q); build(q); t^.r:=q; end;
          Ins(t^.r,(b+e) shr 1+1,e,k);
        end;
    inc(t^.s);
end;
 
Procedure Del(t:ptype; b,e,p:longint);
Var i,j,k:longint;
begin
    if b=e then begin dec(t^.s); exit; end;
    if t^.l=nil then k:=0
                else k:=t^.l^.s;
 
    if p<=k then Del(t^.l,b,(b+e) shr 1,p)
            else Del(t^.r,(b+e) shr 1+1,e,p-k);
 
    dec(t^.s);
end;
 
Function Rfs(t:ptype; b,e,p:longint):longint;
var i,j,k:longint;
begin
    if b=e then exit(t^.k);
    if t^.l=nil then k:=0 else k:=t^.l^.s;
    if p<=k then exit(rfs(t^.l,b,(b+e) shr 1,p))
            else exit(rfs(t^.r,(b+e) shr 1+1,e,p-k));
end;

染色问题（黑/白）: