PKU 2777 线段树（一） 概述 基本操作

[PKU 2777] 线段树(一) {概述 基本操作}

{

以前写的线段树都是零碎 而且描述的也不清楚 最近打算整理一下

就从我的第一个线段树程序开始吧 }

线段树 Segment_tree

网上有人把线段树翻译成 Interval_Tree

Interval_Tree 是另外一种数据结构 而且并非二叉树 这个是线段树的标准E文翻译

可以看wikipedia的原文 http://en.wikipedia.org/wiki/Segment_tree 顾名思义 线段树存储的是连续的线段而非离散的节点 先看一张经典的线段树图解

这个就是标准的线段树

既然是树形结构 我们就得先考虑怎么存储这棵树 分析线段树的定义

*线段树是一棵二叉树 记为T(a, b)

*参数a,b表示区间[a,b] 其中b-a称为区间的长度 记为L *线段树T(a,b)也可递归定义为

-若L>1 [a, (a+b) div 2]为T的左儿子 [(a+b) div 2,b]为T的右儿子 -若L=1 T为叶子节点 可以得到一些基本性质

*线段树除最后一层外是满二叉树 *线段树是平衡的 高度是Log2L左右 如此我们有2种存储方法 *直接用指针 定义节点

type node=record ls,rs:^node; l,r:longint; end;

其中ls rs分别为左右儿子 l,r是区间的范围 真正实现时一般用数组模拟指针

我们只需定义longint数组ls[] rs[] l[] r[] *用*2和*2+1代替左右儿子指针 由于是除最后一层外是满二叉树 我们可以向存储堆一样存储线段树 用l[] r[]来存储节点区间范围

x的左右儿子分别就是x*2和x*2+1 具体实现用位移代替乘2

这样乘法指针运算和上述数组调用一样 几乎不需要时间 具体用哪种纯粹是个人喜好 没什么区别

(下文中我的程序都是用的数组模拟 直接存储儿子指针)

接下来讨论线段树的具体操作

也就是维护这种数据结构的算法 (srO 数据结构+算法=程序 Orz) 总结起来就两个词 递归 & 分治 结合一个具体问题吧 PKU 2777 http://poj.org/problem?id=2777

来源：POJ2777 【问题描述】

一个有L个格子的染色板，每个格子编号为1,2,3……L，每个格子初始都染成了1号色。一共有T种不同的颜色，编号分别为1,2,3……T。可进行O次操作。对染色板的操作有2种。 （1）C(a,b,c) 意思是将染色板中编号为a~b的所有格子染成c号色(1≤a≤b≤L,1≤c≤T) （2）P(a,b)意思是查询染色板中编号为a~b的格子染成的颜色种数。(1≤a≤b≤L) 【输入】

第一行有三个正整数，分别为L，T，O。

接下来有O行，每行为C a b c或P a b。（C、P是字母，a,b,c均为正整数） 【输出】

输出有若干行，分别回答输入中每个查询的结果。 【样例输入】 6 4 5 C 1 2 2 C 2 3 3

P 1 3 C 3 6 4 P 1 6 【样例输出】 2 3

【数据规模】

1≤L≤100,000 1≤T≤30 1≤O≤100,000

这是线段树的入门题 相当经典 要求程序实现一个涂色的程序

支持对区间[A,B]涂C的颜色和统计区间[A,B]的颜色种类 朴素的做法是用数组a[]存储下整个区间[0,100000] 然后循环涂色 循环查询 这样的复杂度是N*N 大大地TLE 我们考虑用线段树处理这个区间问题 首先我们得建树 先看程序

1 procedure build(a,b:longint); 2 var x,mid:longint; 3 begin

4 inc(tt); x:=tt; 5 l[x]:=a; r[x]:=b; 6 if b-a>1 7 then begin 8 mid:=(a+b)shr 1;

9 ls[x]:=tt+1; build(a,mid); 10 rs[x]:=tt+1; build(mid,b);

11 end; 12 end;

*第一行build函数是一个递归的过程 参数a,b表示当前建立区间[a,b]的节点 *第四行 inc(tt) 就相当于新建一个节点 x纪录当前节点 *第六行 b-a=1 是递归的边界条件 即建立到叶子节点了 *第八 九 十行 根据线段树定义 分别递归建立左右儿子区间

-注意儿子指针的赋值 由于递归下去第一层就是建立当前节点的儿子 直接赋值为tt+1即可 -注意使用shr运算提高效率 还需注意a b mid 皆为区间端点

其实上文中建好的线段树其实是一个骨架

就相当于朴素做法中我们还未操作的空数组 等待我们给它刷颜色

既然要刷颜色 我们就得存储各区间的颜色 给每个节点新开一个域n来记录颜色 表现在数组模拟上就是新建数组n[] n数组代表当前节点所代表区间的颜色 因为这个问题的染色是覆盖类型的染色

对一个区间染色自然把为当前区间的子区间也染色了 所以是对子树染色而非区间染色 接着这样的思路 我们可以写出如下程序

1 procedure insert(x,a,b,c:longint); 2 var mid:longint; 3 begin

4 if (a<=l[x])and(r[x]<=b) 5 then n[x]:=c; 6 mid:=(l[x]+r[x])shr 1;

7 if a

8 if b>mid then insert(rs[x],a,b,c); 9 end;

*第四 五行 判断当前区间是否在需要覆盖的区间内 是就修改颜色

*第六 七 八行 根据线段树定义判断是否递归左右子树染色 这里需要说明一下这种写法的正确性

即不会出现[a,b]在[l[x],r[x]]外与当前区间没有交集的情况 首先在根节点处[a,b]和区间显然有交集

然后运用数学归纳法的思路 说明当前节点区间和[a,b]有交集的时候 递归插入儿子也是保证和儿子区间有交集的

这样只要执行插入函数就有交集 就能保证程序正确性

给出所有和当前区间有交集的情况图 可以发现经过if语句判断 递归插入都保证还是和儿子区间有交集 (黑色为当前区间 红色为欲染色区间 一共6种情况)

不难分析出这个插入函数的复杂度是O(N)级别的(需要遍历子树) 从常数上看比朴素还慢 但是不覆盖子树上的区间又会产生错误 我们需要对插入进行改进 改进后 我们的n[]数组不单记录一个节点的颜色 而是记录的子树的颜色 我们看具体操作

*如果当前区间已经染色且颜色和欲染色一致 则直接退出(这句话可以不要) *如果当前区间被完全覆盖 就说明子树也被完全覆盖了 直接给当前节点染色退出

*如果没有被完全覆盖

-就给先给左右儿子染色成当前节点的颜色 然后当前节点赋值为混合颜色=-1 -然后再递归染色左右子树

这样修改完全覆盖的区间时就可以直接修改然后退出 不用遍历子树了

而没有完全覆盖时 需要把颜色先下传给左右子树 再递归修改 保证子树颜色的正确性 这样我们访问的区间总数就降到了O(LogN)级别个 比O(N)好了不少 这个其实是一种最原始的Lazy-Tag思想 这种思想很重要 也比较难掌握 我们以后详细讨论 给出改进后的代码

1 procedure down(x:longint); 2 begin 3 if n[x]>0 4 then begin 5 n[ls[x]]:=n[x]; 6 n[rs[x]]:=n[x]; 7 n[x]:=-1; 8 end; 9 end;

1 procedure insert(x,a,b,c:longint); 2 var mid:longint; 3 begin

4 if (a<=l[x])and(r[x]<=b) 5 then n[x]:=c 6 else begin

7 down(x);

8 mid:=(l[x]+r[x])shr 1;

9 if amid then insert(rs[x],a,b,c); 11 end; 12 end;

最后就是统计了

统计相对很简单 一共30种颜色 用个Simple Hash即可 这时候我们记录的混合颜色就有用了 用于判断

结构和插入差不多 不过递归的条件不再是是否有交集而是是否为空节点了

1 procedure count(x,a,b:longint); 2 var mid:longint; 3 begin

4 if x=0 then exit; 5 if n[x]>0

6 then inc(h[n[x]]) 7 else begin

8 mid:=(l[x]+r[x])shr 1;

9 if amid then count(rs[x],a,b); 11 end; 12 end;

最后是我的AC代码

1 const max=200000;

2 var l,r,ls,rs,n:array[1..max]of longint; 3 m,t,z,tt,k,i,x,y,ans:longint; 4 h:array[1..30]of longint; 5 ch:char;

6 procedure build(a,b:longint); 7 var x,mid:longint; 8 begin

9 inc(tt); x:=tt; 10 l[x]:=a; r[x]:=b; 11 if b-a>1 12 then begin 13 mid:=(a+b)shr 1;

14 ls[x]:=tt+1; build(a,mid); 15 rs[x]:=tt+1; build(mid,b); 16 end; 17 end;

18 procedure down(x:longint); 19 begin 20 if n[x]>0 21 then begin 22 n[ls[x]]:=n[x]; 23 n[rs[x]]:=n[x]; 24 n[x]:=-1; 25 end; 26 end;

27 procedure insert(x,a,b,c:longint); 28 var mid:longint; 29 begin

30 if (a<=l[x])and(r[x]<=b)

31 then n[x]:=c 32 else begin 33 down(x);

34 mid:=(l[x]+r[x])shr 1;

35 if amid then insert(rs[x],a,b,c); 37 end; 38 end;

39 procedure count(x,a,b:longint); 40 var mid:longint; 41 begin

42 if x=0 then exit; 43 if n[x]>0

44 then inc(h[n[x]]) 45 else begin

46 mid:=(l[x]+r[x])shr 1;

47 if amid then count(rs[x],a,b); 49 end; 50 end; 51 begin

52 assign(input,'color.in'); reset(input); 53 assign(output,'color.out'); rewrite(output); 54 readln(m,t,k); 55 tt:=0; 56 build(0,m); 57 n[1]:=1; 58 while k>0 do 59 begin 60 dec(k);

61 read(ch); 62 read(x,y);

63 if ch='C' then read(z); 64 readln; 65 case ch of 66 'C':

67 insert(1,x-1,y,z); 68 'P': 69 begin

70 fillchar(h,sizeof(h),0); 71 count(1,x-1,y); 72 ans:=0;

73 for i:=1 to t do

74 if h[i]>0 then inc(ans); 75 writeln(ans); 76 end; 77 end; 78 end;

79 close(input); close(output); 80 end. 81

这就是线段树的入门题

接下来会具体讨论线段树的另一个经典问题 求矩形并面积和周长

需要用到线段删除和维护更多的域

本文来源：https://www.bwwdw.com/article/gim2.html