资源描述
线 段 树 及 其 应 用江 苏 省 华 罗 庚 中 学 为 什 么 要 用 线 段 树 ?例 1: 有 M个 数 排 成 一 列 , 初 始 值 全 为 0, 然 后 做 N次 操 作 , 每 次 我 们 可 以 进 行 如 下 操 作 :( 1) 将 指 定 区 间 的 每 个 数 加 上 一 个 值 ;( 2) 将 指 定 区 间 的 所 有 数 置 成 一 个 值 ;( 3) 询 问 一 个 区 间 上 的 最 小 值 、 最 大 值 、 所 有 数的 和 。 为 什 么 要 用 线 段 树 ?一 般 的 模 拟 算 法 : 用 一 张 线 性 表 表 示 整 个 数 列 , 每 次 执 行 前 两 个操 作 的 时 候 , 将 对 应 区 间 里 的 数 值 逐 一 进 行 修 改 ,执 行 第 三 个 操 作 的 时 候 , 线 性 扫 描 询 问 区 间 , 求 出三 个 统 计 值 , 每 次 维 护 的 时 间 复 杂 度 O(m), 整 体的 时 间 复 杂 度 O(mn)。 为 什 么 要 用 线 段 树 ?readln(m,n);for i:=1 to n dobegin read(t); if t=1 /指 定 区 间 加 上 一 个 值 then begin readln(left,right,x); for j:=left to right do aj:=aj+x; end; if t=2 /指 定 区 间 置 成 一 个 值then begin readln(left,right,x); for j:=left to right do aj:=x; end; 为 什 么 要 用 线 段 树 ?if t=3 /询 问 一 个 区 间 的 最 小 值 、 最 大 值 、 和then begin readln(left,right); min:=aleft; max:=aleft; sum:=aleft; for j:=left+1 to right do begin if ajmax then max:=aj; sum:=sum+aj; end; writeln(min, ,max, ,sum); end; 为 什 么 要 用 线 段 树 ?机 器 配 置 : Pentium 1.3G 512MM,N的 规 模 一 般 的 模 拟M=100000,N=5000 2.06秒M=100000,N=10000 4.14秒M=100000,N=50000 21.32秒M=100000,N=100000 43.36秒 为 什 么 要 用 线 段 树 ? 当 m、 n的 值 比 较 大 时 , 这 个 算 法 就 太 低 效 了 。其 低 效 的 原 因 主 要 是 我 们 在 每 一 次 操 作 中 都 是 针 对每 个 元 素 进 行 维 护 的 , 而 这 里 我 们 进 行 的 操 作 都 是针 对 一 个 区 间 进 行 操 作 的 。 假 如 设 计 一 种 数 据 结 构 , 能 够 直 接 维 护 所 需 处理 的 , 那 么 就 能 更 加 有 效 地 解 决 这 个 问 题 。 线 段 树 的 结 构定 义 1: 长 度 为 1的 线 段 称 为 元 线 段 。定 义 2: 一 棵 树 被 称 为 线 段 树 , 当 且 仅 当 这 棵 树 满足 如 下 条 件 : ( 1) 该 树 是 一 棵 二 叉 树 ; ( 2) 树 中 的 每 一 个 结 点 都 对 应 一 条 线 段 a,b; ( 3) 树 中 的 结 点 是 叶 子 结 点 , 当 且 仅 当 它 所 代表 的 线 段 是 元 线 段 ; ( 4) 树 中 非 叶 子 结 点 都 有 左 右 两 棵 子 树 , 左 子树 树 根 对 应 线 段 a,(a+b)/2, 右 子 树 树 根 对 应 线 段(a+b)/2,b。 线 段 树 的 结 构如 T(1,10)的 结 构 : 1,10 1,5 5,10 1,3 3,5 5,7 7,10 1,2 2,3 3,4 4,5 5,6 6,7 7,8 8,10 8,9 9,10 线 段 树 的 结 构 常 用 的 是 需 要 对 数 列 进 行 处 理 , 将 区 间 a,b分解 为 a,(a+b)/2, (a+b)/2+1,b, 当 a=b时 表 示 为 一个 叶 子 结 点 , 表 示 数 列 中 的 一 个 数 。1,10 1,5 6,10 1,3 4,5 6,8 9,10 1,2 3,3 4,4 5,5 6,7 8,8 9,9 10,10 1,1 2,2 6,6 7,7 线 段 树 的 性 质性 质 1: 长 度 范 围 为 1,L的 一 棵 线 段 树 的 深 度 不 超过 log2(L-1)+1;性 质 2: 线 段 树 上 的 结 点 个 数 不 超 过 2L个 ;性 质 3: 线 段 树 把 区 间 上 的 任 意 一 条 线 段 都 分 成 不超 过 2log2L条 线 段 。 线 段 树 的 存 储 方 式( 1) 链 表 实 现 : Node=TNode; TNode=record Left,Right:integer; LeftChild,RightChild:Node; end;( 2) 数 组 模 拟 链 表 :Left,Right,LeftChild,RightChild:array1.n of integer;( 3) 堆 的 结 构 :根 节 点 为 1, 对 于 结 点 x, 其 左 孩 子 为 2x, 右 孩 子 为2x+1 线 段 树 的 基 本 操 作 及 实 现线 段 树 的 构 造procedure build(cur:Node;l,r:integer);begin cur.Left:=l; cur.Right:=r; if l=r then begin cur.LeftChild:=nil; cur.RightChild:=nil; end else begin new(cur.LeftChild); new(cur.RightChild); build(cur.LeftChild,l,(l+r) div 2); build(cur.RightChild,(l+r) div 2+1,r); end; end; 线 段 树 的 基 本 操 作 及 实 现线 段 树 的 查 询procedure query(cur:Node;l,r:integer);var LC,RC:Node;begin LC:=cur.LeftChild; RC:=cur.RightChild; if (l=cur.Left) and (cur.Right=r) then writeln(cur.Left, ,cur.Right); /可 以 增 加 其 他 操 作 else begin if l(cur.Left+cur.Right) div 2 then query(RC,l,r); end;end; 线 段 树 的 维 护 方 法对 区 间 进 行 修 改对 元 素 进 行 修 改 设 置 为 同 一 个 数统 一 加 上 一 个 数修 改查 询 区 间 的 和区 间 的 最 大 值区 间 的 最 小 值其 它 线 段 树 的 维 护 方 法 如 果 想 要 让 线 段 树 发 挥 实 际 的 作 用 , 必 须 在 每个 结 点 上 维 护 额 外 的 域 来 记 录 更 多 的 信 息 。 首 先 看 一 个 引 例 的 弱 化 版 , 假 设 每 次 修 改 操 作只 能 对 其 中 某 个 元 素 进 行 修 改 。 在 每 个 结 点 上 额 外 维 护 3个 域 : max、 min、sum, 分 别 表 示 子 树 上 的 最 大 值 、 最 小 值 和 所 有 元素 的 和 。 ( 1) 对 元 素 进 行 修 改procedure insert(cur:Node;x,num:integer);var LC,RC:Node;begin LC:=cur.LeftChild; RC:=cur.RightChild; if cur.Left=cur.Right /对 叶 结 点 的 处 理 then begin cur.Min:=num; cur.Max:=num; cur.Sum:=num; end else begin if x(cur.Left+cur.Right) div 2 then insert(RC,x,num); cur.Sum:=LC.Sum+RC.Sum; /上 推 if (LC.MaxRC.Max) then cur.Max:=LC.Max else cur.Max:=RC.Max; if (LC.MinRC.Min) then cur.Min:=LC.Min else cur.Min:=RC.Min; end;end; ( 2) 对 区 间 进 行 查 询function querysum(cur:Node;l,r:integer):integer;var LC,RC:Node; ret:integer;begin LC:=cur.LeftChild; RC:=cur.RightChild; ret:=0; if (l=cur.Left) and (cur.Right=r) then ret:=cur.Sum else begin if l(cur.Left+cur.Right) div 2 then ret:=ret+querysum(RC,l,r); end; querysum:=ret;end; ( 3) 对 区 间 修 改 ( 统 一 加 上 一 个 数 )procedure update(cur:Node;l,r,delta:integer);var LC,RC:Node; /需 要 给 每 个 区 间 增 加 一 个 变 量 deltabegin LC:=cur.LeftChild; RC:=cur.RightChild; if (l=cur.Left) and (cur.Right=r) then cur.Delta:=cur.Delta+delta /改 变 该 区 间 的 delta, 注 意 sum else begin if l(cur.Left+cur.Right) div 2 then update(RC,l,r,delta); cur.Sum:=LC.Sum+LC.Delta*(LC.Right-LC.Left+1); cur.Sum:=cur.Sum+RC.Sum+ /上 推 RC.Delta*(RC.Right-RC.Left+1); end;end; ( 4) 对 区 间 查 询function querysum(cur:Node;l,r:integer):integer;var LC,RC:Node; ret:integer;begin LC:=cur.LeftChild; RC:=cur.RightChild; ret:=0; if (l=cur.Left) and (cur.Right=r) then ret:=ret+cur.Sum+(cur.Right-cur.Left+1)*cur.Delta else begin /将 该 区 间 的 delta下 传 给 左 右 区 间 , 同 时 修 改 sum的 值 cur.sum:=cur.sum+(cur.right-cur.left+1)*cur.delta; LC.Delta:=LC.Delta+cur.Delta; RC.Delta:=RC.Delta+cur.Delta; cur.Delta:=0; if l(cur.Left+cur.Right) div 2 then ret:=ret+querysum(RC,l,r); end; querysum:=ret;end; ( 5) 对 区 间 修 改 ( 设 置 为 同 一 个 数 )procedure update(cur:Node;l,r,num:integer);var LC,RC:Node;begin LC:=cur.LeftChild; RC:=cur.RightChild; if cur.En /如 果 该 区 间 已 经 是 同 一 个 值 , 将 值 下 传 给 左 右 区 间 then begin cur.sum:=(cur.right-cur.left+1)*cur.data; if LCnil then begin LC.Data:=cur.Data; LC.En:=true; end; if RCnil then begin RC.Data:=cur.Data; RC.En:=true; end; cur.En:=false; end; if (l=cur.Left) and (cur.Right=r) then begin cur.En:=true; cur.Data:=num; end else begin if l(cur.Left+cur.Right) div 2 then update(RC,l,r,num); cur.Sum:=calcsum(LC)+calcsum(RC); end;end; function calcsum(cur:Node):integer;begin if cur.En then calcsum:=(cur.Right-cur.Left+1)*cur.Data else calcsum:=cur.Sum;end; ( 6) 对 区 间 查 询function querysum(cur:Node;l,r:integer):integer;var LC,RC:Node; ret:integer;begin LC:=cur.LeftChild; RC:=cur.RightChild; ret:=0; if (l=cur.Left) and (cur.Right=r) then ret:=ret+calcsum(cur) else begin if cur.En /如 果 该 区 间 是 同 一 个 数 , 将 值 下 传 给 左 右 区 间 then begin LC.Data:=cur.Data; LC.En:=true; RC.Data:=cur.Data; RC.En:=true; cur.En:=false; end; if l(cur.Left+cur.Right) div 2 then ret:=ret+querysum(RC,l,r); end; querysum:=ret;end; 线 段 树 的 维 护 方 法线 段 树 上 的 参 数 通 常 有 两 种 维 护 方 法 :( 1) 一 类 参 数 表 达 了 结 点 的 性 质 , 通 常 具 有 树 型的 递 推 性 质 , 可 以 从 下 向 上 进 行 递 推 计 算 ; ( 如sum,max,min)( 2) 一 类 参 数 表 达 了 子 树 的 性 质 , 维 护 的 时 候 可以 先 打 上 标 记 , 在 需 要 进 一 步 访 问 其 子 结 点 的 时 候从 上 向 下 传 递 。 ( 如 delta,en) 线 段 树 的 维 护 方 法线 段 树 上 维 护 或 者 询 问 过 程 的 一 般 过 程 :对 于 当 前 区 间 l,rif 达 到 某 种 边 界 条 件 ( 如 叶 结 点 或 被 整 个 区 间 完 全 包 含 )then 对 维 护 或 是 询 问 作 相 应 处 理else 将 第 二 类 标 记 传 递 下 去 (注 意 , 在 查 询 过 程 中 也 要 处 理 ) 根 据 区 间 的 关 系 , 对 两 个 孩 子 结 点 递 归 处 理 利 用 递 推 关 系 , 根 据 孩 子 结 点 的 情 况 维 护 第 一 类 信 息 为 什 么 要 用 线 段 树 ?M,N的 规 模 一 般 的 模 拟 线 段 树M=100000,N=5000 2.06秒 0. 57秒M=100000,N=10000 4.14秒 0. 61秒M=100000,N=50000 21.32秒 1.21秒M=100000,N=100000 43.36秒 2.03秒 应 用 举 例例 2、 线 段 覆 盖 在 所 有 不 大 于 30000的 自 然 数 范 围 内 讨 论 一 个问 题 : 已 知 n条 线 段 , 把 端 点 依 次 输 入 告 诉 你 , 然后 有 m( 30000) 个 询 问 , 每 个 询 问 输 入 一 个 点 ,要 求 这 个 点 在 多 少 条 线 段 上 出 现 过 。 0 1 2 3 4 5 6 7 8n=4 m=3线 段 : 0,3 4,6 2,6 5,7询 问 : 1, 3, 5 应 用 举 例 ( 线 段 覆 盖 ) 可 以 直 接 对 问 题 处 理 的 区 间 建 立 线 段 树 , 在 线段 树 上 维 护 区 间 被 覆 盖 的 次 数 。 将 n条 线 段 插 入 线段 树 , 然 后 对 于 询 问 的 每 个 点 , 直 接 查 询 被 覆 盖 的次 数 即 可 。 应 用 举 例 ( 线 段 覆 盖 ) 这 道 题 目 完 全 可 以 不 用 线 段 树 , 将 每 个 线 段 拆分 成 (L,+1), (R+1,-1)的 两 个 事 件 点 , 每 个 询 问 点也 在 对 应 坐 标 处 加 上 一 个 询 问 的 事 件 点 , 排 序 之 后扫 描 就 可 以 完 成 题 目 的 询 问 。 Sum 1 1 2 2 2 3 3 1 0 +1-1 -1 -10 1 2 3 4 5 6 7 8+1 +1+1 -1 应 用 举 例 ( 线 段 覆 盖 ) 因 为 此 问 题 是 一 个 离 线 的 问 题 , 这 是 一 个很 简 单 的 离 线 算 法 。 线 段 树 在 处 理 在 线 问 题 的时 候 会 更 加 有 效 , 因 为 它 维 护 了 一 个 实 时 的 信息 。 应 用 举 例例 3、 售 票 系 统 某 次 列 车 途 经 C个 城 市 , 城 市 编 号 依 次 为 1到 C,列 车 上 共 有 S个 座 位 , 每 一 个 售 票 申 请 包 含 三 个 参数 , 分 别 用 O、 D、 N表 示 , O为 起 始 站 , D为 目 的地 站 , N为 车 票 张 数 , 售 票 系 统 对 该 售 票 申 请 作 出受 理 或 不 受 理 的 决 定 。 只 有 在 从 O到 D的 区 段 内 列车 上 都 有 N个 或 N个 以 上 的 空 座 位 时 该 售 票 申 请 才被 受 理 。 1=C=60000, 1=S=60000,1=R=60000, C为 城 市 个 数 , S为 列 车 上 的 座 位数 , R为 所 有 售 票 申 请 总 数 。 应 用 举 例 ( 售 票 系 统 )输 入 :4 6 41 4 21 3 22 4 31 2 3 输 入 :YESYESNONO 应 用 举 例 ( 售 票 系 统 ) 可 以 把 所 有 的 车 站 顺 次 放 在 一 个 数 轴 上 , 在 数轴 上 建 立 线 段 树 , 在 线 段 树 上 维 护 区 间 的 delta与max, 每 次 判 断 一 个 售 票 申 请 是 否 可 行 就 是 查 询 区间 上 的 最 大 值 ; 每 个 插 入 一 个 售 票 请 求 , 就 是 给 一个 区 间 上 所 有 的 元 素 加 上 购 票 数 。 应 用 举 例 ( 售 票 系 统 )procedure build(cur:node;l,r:longint);begin cur.left:=l; cur.right:=r; if l=r then begin cur.leftchild:=nil; cur.rightchild:=nil; cur.delta:=0; cur.max:=0; end else begin new(cur.leftchild); new(cur.rightchild); build(cur.leftchild,l,(l+r) div 2); build(cur.rightchild,(l+r) div 2+1,r); end;end; 应 用 举 例 ( 售 票 系 统 )procedure update(cur:node;l,r,delta:longint);var lc,rc:node;begin lc:=cur.leftchild; rc:=cur.rightchild; if (l=cur.right) then begin cur.delta:=cur.delta+delta; cur.max:=cur.max+delta; end else begin if l(cur.left+cur.right) div 2 then update(rc,l,r,delta); if lc.maxrc.max then cur.max:=lc.max+cur.delta else cur.max:=rc.max+cur.delta; end;end; function querymax(cur:node;l,r:longint):longint;var lc,rc:node; ret:longint;begin lc:=cur.leftchild; rc:=cur.rightchild; ret:=0; if (l=cur.left) and (cur.right=r) then ret:=cur.max else begin lc.delta:=lc.delta+cur.delta;rc.delta:=rc.delta+cur.delta; lc.max:=lc.max+cur.delta; rc.max:=rc.max+cur.delta; cur.delta:=0; if l(cur.left+cur.right) div 2 then if rets then writeln(NO) else begin writeln(YES); update(tree,a,b-1,x); end; end;end. 算 法 改 进Function test(cur:node;l,r,x,remain:longint):boolean;var lc,rc:node; ret:boolean;begin lc:=cur.leftchild; rc:=cur.rightchild; ret:=true; if (l=cur.right) then if cur.max+xremain then ret:=false else ret:=true else if (remain-cur.delta=0) then begin if l(cur.left+cur.right) div 2 then ret:=ret and test(rc,l,r,x,remain-cur.delta) end; test:=ret;end; 应 用 举 例例 4、 采 矿 金 矿 的 老 师 傅 年 底 要 退 休 了 。 经 理 为 了 奖 赏 他的 尽 职 尽 责 的 工 作 , 决 定 送 他 一 块 长 方 形 地 。 长 度为 S, 宽 度 为 W。 老 师 傅 可 以 自 己 选 择 这 块 地 。 显然 其 中 包 含 的 采 金 点 越 多 越 好 。 你 的 任 务 就 是 计 算最 多 能 得 到 多 少 个 采 金 点 。 如 果 一 个 采 金 点 的 位 置在 长 方 形 的 边 上 , 它 也 应 当 被 计 算 在 内 。读 入 采 金 点 的 位 置 。 计 算 最 大 的 价 值 。 数 据 范 围 : 1=s,w=10 000 1=s,w=10 000 -30 000=x,y=30 000 应 用 举 例 ( 采 矿 ) L1 L2S W 应 用 举 例 ( 采 矿 )对 于 每 一 个 点 的 纵 坐 标 y,建 立 两 个 事 件 点 (y,+1), (y+w+1,-1)如 5个 点 的 纵 坐 标 分 别 是 (5,3,9,1,9),w=2得 到 10个 事 件 点 : (5,+1),(8,-1),(3,+1),(6,-1),(9,+1),(12,-1),(1,+1),(4,-1),(9,+1),(12,-1)1 2 3 4 5 6 7 8 9 10 11 12+1 +1 -1 +1 -1 -1 +2 -2然 后 从 低 到 高 求 和 , 这 些 和 中 最 大 的 一 个 就 是 该带 状 区 域 中 一 个 包 含 最 多 点 数 的 矩 形 。 1 2 1 2 1 0 +2 0 应 用 举 例例 5、 面 积 平 面 上 有 若 干 个 平 行 于 坐 标 轴 的 矩 形 , 它 们 可以 相 互 重 叠 且 每 个 矩 形 顶 点 的 坐 标 都 是 整 数 , 求 这些 矩 形 覆 盖 的 总 面 积 。输 入 :210 10 20 2015 15 25 30 输 出 :225 应 用 举 例 ( 面 积 ) 10 15 20 25 应 用 举 例 ( 面 积 ) 先 把 坐 标 离 散 化 , 然 后 从 左 往 右 扫 描 每 一条 垂 直 于 X轴 的 线 段 , 如 果 一 条 线 段 是 矩 形 的左 边 界 , 则 插 入 线 段 ; 如 果 是 矩 形 的 右 边 界 ,则 删 除 线 段 。 取 得 线 段 的 长 度 即 可 得 到 当 前 离散 条 的 面 积 。 定 义 add、 del两 个 数 组 分 别 记 录 每 个 矩 形的 左 边 界 、 右 边 界 。输 入 :210 10 20 2015 15 25 30 add10,1.h1=10; add10,1.h2=20;del20,1.h1=10; del20,1.h2=20;add15,1.h1=15; add15,1.h2=30;del25,1.h1=15; del25,1.h2=30; 应 用 举 例 ( 面 积 )procedure build(cur:node;l,r:longint);begin cur.left:=l; cur.right:=r; if l+1=r then begin cur.leftchild:=nil; cur.rightchild:=nil; cur.delta:=0; cur.sum:=0; end else begin new(cur.leftchild); new(cur.rightchild); build(cur.leftchild,l,(l+r) div 2); build(cur.rightchild,(l+r) div 2,r); end; end; procedure update(cur:node;l,r,t:longint);var lc,rc:node;begin lc:=cur.leftchild; rc:=cur.rightchild; if (l=cur.left) and (cur.right=r) then if t=0 then dec(cur.delta) else inc(cur.delta) else begin if l(cur.left+cur.right) div 2 then update(rc,l,r,t); if lc.delta0 then cur.sum:=lc.right-lc.left else cur.sum:=lc.sum; if rc.delta0 then cur.sum:=cur.sum+rc.right-rc.left else cur.sum:=cur.sum+rc.sum; end;end; 应 用 举 例 ( 面 积 )主 程 序 :for i:=1 to 30000 dobegin addi:=nil; deli:=nil;end;readln(n);for i:=1 to n dobegin readln(x1,y1,x2,y2); new(p); p.h1:=y1; p.h2:=y2; p.next:=addx1; addx1:=p; new(p); p.h1:=y1; p.h2:=y2; p.next:=delx2; delx2:=p; end; new(tree); build(tree,0,30000); sum:=0;for i:=0 to 30000 dobegin p:=deli; while pnil do begin update(tree,p.h1,p.h2,0); p:=p.next; end; p:=addi; while pnil do begin update(tree,p.h1,p.h2,1); p:=p.next; end; if tree.delta0 then sum:=sum+30000 else sum:=sum+tree.sum; end;writeln(sum); 应 用 举 例例 6、 蛇在 平 面 上 有 N个 点 , 现 在 要 用 一 些 线 段 将 它 们 连 起 来 ,使 其 满 足 以 下 要 求 :( 1) 这 些 线 段 必 须 闭 合( 2) 线 段 的 端 点 只 能 是 这 N个 点( 3) 交 于 一 点 的 两 条 线 段 成 90度 角( 4) 线 段 都 必 须 平 行 于 X轴 或 Y轴( 5) 所 有 线 段 除 了 在 这 N个 点 外 不 相 交( 6) 所 有 线 段 的 长 度 之 和 必 须 最 短如 果 存 在 这 样 的 线 段 , 则 输 出 最 小 长 度 , 否 则 输 出 0。 XY 应 用 举 例 ( 蛇 )1、 所 有 线 段 都 要 和 坐 标 轴 平 行 , 所 以 每 个 点 只 能与 上 下 左 右 四 个 点 相 连 , 由 于 与 一 个 点 相 连 的 两 条线 段 成 90度 , 每 个 顶 点 必 须 与 一 条 平 行 于 X轴 和 一条 平 行 于 Y轴 的 线 段 相 连 。2、 在 同 一 水 平 线 上 的 点 中 , 按 X轴 排 序 后 设 为 P1,P2, Pn, P1必 须 与 P2相 连 , P3必 须 与 P4相连 , 在 同 一 垂 直 线 上 的 点 也 同 样 , 所 以 线 段 的 构 造是 唯 一 的 。 应 用 举 例 ( 蛇 )3、 由 于 解 是 唯 一 的 , 是 否 相 连 只 要 广 度 扩 展 就 可判 断 了 , 关 键 在 于 判 断 由 上 述 方 法 所 构 造 出 的 线 段是 否 合 法 ( 满 足 线 段 不 在 N个 点 之 外 自 交 ) 。不 相 连 不 合 法 不 自 交 合 法 自 交 不 合 法 应 用 举 例 ( 蛇 )4、 由 于 所 有 线 段 与 坐 标 轴 平 行 , 有 明 显 的 区 间 性 ,可 以 用 线 段 树 判 断 是 否 自 交 :( 1) 先 将 所 有 的 线 段 按 X坐 标 排 序 , 注 意 线 段 在端 点 重 合 不 算 自 交 , 所 以 X轴 坐 标 相 同 时 , 事 件 的顺 序 要 恰 当 处 理 : 右 端 点 优 先 , 其 次 是 与 Y轴 平 行的 线 段 , 最 后 是 左 端 点 。S1 S2S3 S4 S5 S1 S2 S3S4 应 用 举 例 ( 蛇 )S1 S2S3S4 S5 S1 S2 S3S4( 2) 将 Y轴 表 示 的 区 间 建 立 线 段 树 , 每 个 线 段 或 线 段 的 端点 作 为 一 个 事 件 。 按 X坐 标 由 小 到 大 , 扫 描 所 有 事 件 : 平 行 于 X轴 线 段 的 左 端 点 , 就 把 Y坐 标 插 入 到 线 段 树 中 ; 平 行 于 X轴 线 段 的 右 端 点 , 就 把 Y坐 标 从 线 段 树 中 删 除 ; 平 行 于 Y轴 的 线 段 , 假 设 该 线 段 的 Y坐 标 分 别 为 y1和 y2,就 在 线 段 树 中 查 询 y1, y2区 间 内 是 否 有 点 存 在 , 如 果 存 在就 说 明 有 线 段 和 它 相 交 , 该 图 形 不 合 法 。 线 段 树 与 RMQ的 比 较 RMQ提 供 了 一 种 高 效 的 计 算 区 间 最 值 的 方 法 。它 的 思 想 是 将 询 问 区 间 分 解 成 两 个 最 大 的 2的 次 幂的 长 度 的 区 间 并 的 形 式 。 与 线 段 树 不 同 , 这 种 区 间分 解 是 存 在 相 交 的 分 解 。 因 此 RMQ只 能 维 护 一 些简 单 的 信 息 , 比 如 最 值 。 线 段 树 与 RMQ的 比 较RMQ的 优 势 :( 1) 实 现 非 常 简 单 ;( 2) 效 率 比 线 段 树 更 高 ;线 段 树 的 优 势 :( 1) 可 以 更 好 地 维 护 动 态 的 信 息 , 而 RMQ不 推 广到 动 态 ;( 2) 可 以 维 护 更 多 的 信 息 , 而 RMQ只 能 维 护 最 值 。 线 段 树 与 树 状 数 组 的 比 较 树 状 数 组 可 以 对 单 个 元 素 进 行 高 效 的 修 改 , 并且 可 以 高 效 的 求 部 分 和 。 由 于 使 用 了 位 运 算 , 因 此 树 状 数 组 的 效 率 要 优于 线 段 树 。 树 状 数 组 的 空 间 开 销 也 比 线 段 树 要 小 , 但 是 树状 数 组 的 应 用 范 围 没 有 线 段 树 广 , 能 够 转 化 使 用 树状 数 组 的 情 况 下 尽 量 使 用 树 状 数 组 。 线 段 树 与 平 衡 树 的 比 较 这 两 种 数 据 结 构 解 决 了 不 同 方 面 的 问 题 , 但 是有 的 题 目 通 过 适 当 的 建 模 , 使 用 两 种 数 据 结 构 都 能够 加 以 解 决 。 通 常 情 况 下 , 使 用 线 段 树 的 效 率 会 优于 平 衡 树 。 但 线 段 树 有 一 点 局 限 性 : 尽 管 能 够 在 区 间 上 进行 修 改 操 作 , 但 不 能 插 入 或 者 删 除 区 间 。 而 这 种 插入 与 删 除 操 作 却 是 平 衡 树 的 基 本 操 作 之 一 。 参 考 资 料线 段 树 : 线 段 树 及 其 应 用 NOI专 刊 2009年 第 1期 线 段 树 及 其 应 用 2009年 冬 令 营 小 营 讲 课 数 据 结 构 ( 七 ) NOI专 刊 2007年 第 7期 Picture题 目 解 析 NOI专 刊 2008年 第 2期RMQ: RMQ在 信 息 学 竞 赛 中 的 应 用 NOI专 刊 2008年 第 8期树 状 数 组 : 树 状 数 组 简 介 NOI专 刊 2008年 第 9期平 衡 树 : 数 据 结 构 ( 六 ) NOI专 刊 2007年 第 6期 晚 间 讨 论 线 段 树 与 数 据 结 构 ( 如 RMQ、 排 序 树 、 平 衡树 、 树 状 数 组 、 堆 ) 的 区 别 和 适 用 题 型 。
展开阅读全文