《线段树及其应用》PPT课件

线 段 树 及 其 应 用江 苏 省 华 罗 庚 中 学 为 什 么 要 用 线 段 树 ？例 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、 排 序 树 、 平 衡树 、 树 状 数 组 、 堆 ） 的 区 别 和 适 用 题 型 。