求Pascal语言线段树模板
发布网友
发布时间：2022-04-23 15:10
共3个回答
热心网友
时间：2023-06-24 18:01
线段树:
0.线段树又称区间树,是一种对动态集合进行维护的二叉搜索树,该集合中的每个元素tree都包含一个区间[x,y].若总线段长为n,则线段树总节点数为2*n
线段树支持下列操作:
1.将包含区间 int 的元素 x 插入到树t中
2.从线段树 t 中删除元素 x
3.返回一个指向树 t 中元素 x 的指针
线段树形式:
p,r:int;
mid:int;
left,right:int;
data:int;
end;
var tree:array[1..2*n] of tnode;
变量解释:p,r表示这棵子树的区间是[p,r),mid表示这条线段的中点[mid:=[p+r] div 2],left,right表示这棵树的左右子树在tree数组中的下标号,data是每棵子树的附加信息,就是让你统计的物质,比如:和.
代码模板
1.线段树的建立(它的附加信息是区间点总数,可以根据需要而改变)
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.查询
变量释义: u,a,b:查询[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.更新
变量释义: u,x,v:x在tree[u]上,把x点和线段树中所有包含x的点的附加信息更新e
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)的问题.
热心网友
时间：2023-06-24 18:02
ProgramIntervalTree;
Const
Inf='Input.txt';
Ouf='Output.txt';
Maxn=10000;
Type
TreeNode=Record
//a,b:区间左右边界，left,right:左右儿子,cover:是否被覆盖
a,b,Left,Right,Cover:Longint;
End;
Var
Tree:array [1..Maxn] of TreeNode;
Number,Tot,c,d:Longint; //tot:线段树节点总数
ProcereMakeTree(a,b:Longint); //建树
Var
Now:Longint; //now必须为局部变量!(dfs中枚举变量一样的道理)
Begin
Inc(Tot); //节点总数+1
Now:=Tot;
Tree[Now].a:=a; Tree[Now].b:=b;Tree[Now].Cover:=0; //把[a,b]数据写入到tree[tot];
If a+1<b then begin
Tree[Now].Left:=Tot+1;
MakeTree(a,(a+b) div 2); //建左子树
Tree[Now].Right:=Tot+1; //(若now为全局变量，建左子树会修改now的值，导致此处建树不正确)
MakeTree((a+b) div 2,b); //建右子树
End;
End;
ProcereInsert(Num:Longint); //插入线段[c,d](c,d为全局变量)到线段树第num个节点区间
Begin
If (c<=Tree[Num].a) and (Tree[Num].b<=d)then //若当前区间被[c,d]覆盖，则cover+1
Tree[Num].Cover:=Tree[Num].Cover+1
Else begin //否则将区间[c,d]插到左右子树中
If c<(Tree[Num].a+Tree[Num].b) div 2 thenInsert(Tree[Num].Left);
If d>(Tree[Num].a+Tree[Num].b) div 2 thenInsert(Tree[Num].Right);
End;
End;
ProcereDelete(Num:Longint);//在线段树第num个节点区间中删除线段[c,d]
Begin
If (c<=Tree[Num].a) and (Tree[Num].b<=d)then //若当前区间被[c,d]覆盖，则cover-1
Dec(Tree[Num].Cover)
Else begin //否则将区间[c,d]在左右子树中删除
If c<(Tree[Num].a+Tree[Num].b) div 2 thenDelete(Tree[Num].Left);
If d>(Tree[Num].a+Tree[Num].b) div 2 thenDelete(Tree[Num].Right);
End;
End;
ProcereCount(Num:longint); //计算整个线段树的测度(被覆盖区间的总长度)
Begin
If Tree[Num].Cover>0 then //若当前区间被完全覆盖，则累加到number全局变量中
Number:=Number+(Tree[Num].b-Tree[Num].a)
Else begin //否则，若为部分覆盖，则累加左右子树的测度
If Tree[Num].Left>0 thenCount(Tree[Num].Left);
If Tree[Num].Right>0 thenCount(Tree[Num].Right);
End;
End;
Begin
Assign(Input,Inf);Reset(Input);
Assign(Output,ouf);Rewrite(Output);
Readln(c,d); //读入总区间大小
MakeTree(c,d); //建树
While not eof do
Begin
Readln(c,d); //向线段树中插入线段[c,d]
Insert(1);
End;
Count(1); //计算线段树的测度
Writeln(Number);
Close(Output);
Close(Input);
End.
热心网友
时间：2023-06-24 18:02
