温存's Blog

线段树又称区间树,是一种对动态集合进行维护的二叉搜索树,该集合中的每个元素tree都包含一个区间[x,y].若总线段长为n,则线段树总节点数为2*n

线段树支持下列操作:
     1.将包含区间 int 的元素 x 插入到树t中
     2.从线段树 t 中删除元素 x
     3.返回一个指向树 t 中元素 x 的指针

线段树形式:

type tnode=record
         p,r:int;  表示这棵子树的区间是[p,r)
         mid:int;  表示这条线段的中点[mid:=[p+r] div 2]
         left,right:int; 表示这棵树的左右子树在tree数组中的下标号
         data:int;是每棵子树的附加信息,就是让你统计的物质
       end;
var tree:array[1..2*n] of tnode;

代码模板:

1.线段树的建立(它的附加信息是区间点总数,可以根据需要而改变)

procedure build(u:int);
begin
  if tree[u].p+1=tree[u].r then
  begin
    tree[u].sum:=1;
    exit;
  end;
  tree[u].m:=(tree[u].p+tree[u].r) div 2;
  inc(top);
  tree[u].left:=top;
  tree[tree[u].left].p:=tree[u].p;
  tree[tree[u].left].r:=tree[u].m;
  build(tree[u].left);
  inc(top);
  tree[u].right:=top;
  tree[tree[u].right].p:=tree[u].m;
  tree[tree[u].right].r:=tree[u].r;
  build(tree[u].right);
 tree[u].sum:=tree[tree[u].left].sum+tree[tree[u].right].sum;
end;

特别注意:在主程序中执行build之前,应先写下如下代码:
top:=1;
tree[1].p:=1;
tree[1].r:=n+1;

2.查询

function query(u,a,b:int):int; //查询[a,b),且[a,b)在tree[u]上
var ans:int;
begin
  if (tree[u].p=a)and(tree[u].r=b) then
    exit(tree[u].sum);
  if (a>=b) then exit(0);
  if b<=tree[u].m then
    ans:=query(tree[u].left,a,b)
  else
    if a>=tree[u].m then
      ans:=query(tree[u].right,a,b)
    else
ans:=query(tree[u].left,a,tree[u].m)+query(tree[u].right,tree[u].m,b);
  exit(ans);
end;

3.更新

procedure modify(u,x,v:int);//x在tree[u]上,把x点和线段树中所有包含x的点的附加信息更新
begin
  if (tree[u].p+1=tree[u].r) then
  begin
    tree[u].sum:=v;
    data[x]:=v;
    exit;
  end;
  if x<tree[u].m then
    modify(tree[u].left,x,v)
  else modify(tree[u].right,x,v);
 tree[u].sum:=tree[tree[u].left].sum+tree[tree[u].right].sum;
end;

注意:线段树用于求解满足ans[l,r]=ans[l,m]+ans[m,r]+f(l,r)的问题.

 

（http://zhidao.baidu.com/link?url=YlvgCpbgK1pJSPRXPE9T4UZSF3aWyjNZgmU_vV8Uh829CIyQXxSuq9kmVERKXrrDfFfJhjM4WLj1pXeondc_8q）