例析线段树及其应用.ppt

例析线段树及其应用 选编材料，仅供内部参考，不宜外传。 例 数列操作问题 假设有一列数{Ai}(1≤i≤n)，支持如下两种操作： 将Ak的值加D。（k, D是输入的数） 输出As+As+1+…+At。（s, t都是输入的数，S≤T） 输入：第一行一个整数n， 第二行为n个整数，表示{Ai}的初始值。 第三行为一个整数m，表示操作数 下接m行，每行描述一个操作，有如下两种情况： ADD k d (表示将Ak加d，1=k=n，d为数) SUM s t （表示输出As+…+At） 输出：对于每一个SUM提问，输出结果 例 数列操作问题（分析） 如果按题目要求直接模拟： 每一个ADD操作的复杂度是O(1) 每一个SUM操作的复杂度是O(N) 可见对于M次SUM询问，复杂度是O(NM) 有没有更好的方法呢？这里我们提出一种称之为线段树的数据结构。 数列操作的线段树定义 线段树定义（续） 线段树是一棵二叉树，记为T(a, b)，参数a,b表示区间[a,b]，其中b-a称为区间的长度，记为L。 线段树T(a,b)也可递归定义为： 若L1 : [a, (a+b) div 2]为 T的左儿子； [(a+b) div 2,b]为T 的右儿子。 若L=1 : T为叶子节点。 数列操作 线段树的建立 我们知道，对于长度为n的线段建立的线段树，至多只有nlogn个节点，故建立线段树的复杂度是O(nlogn) 数列操作问题的进一步分析 我们用线段树来维护序列。 给线段树的每个节点增加一个域Tree[i].S，表示该区间内所有值的和。 对于ADD k d操作，只需要从根节点开始遍历线段树中每个包含了k的区间节点，然后修改S域。 由于这样的区间至多只有logn个，所以一次ADD操作的复杂度是O(logn) 数列树结构的 SUM操作 对于待计算的区间[s,t]： Function getsum(v):integer; if (s=Tree[v].a) and (Tree[v].b=t) then getsum:=Tree[v].S else begin tot:=0; if [s,t]和Tree[v].Left表示的区间相交 then tot:=tot+getsum(Tree[v].Left); if [s,t]和Tree[v].Right表示的区间相交 then tot:=tot+getsum(Tree[v].Right); getsum:=tot end; 我们不难发现这个过程中所遍历到的区间数（节点数）和线段树的深度同阶，因此时间复杂度是O(logn) 数列操作问题的解决 综上，M次操作的时间复杂度为O(Mlogn) 通过引入线段树的数据结构，虽然ADD操作的复杂度提高到了O(logn)。但SUM操作变得更快(O(logn))。从而也使得算法在大数据处理上更加高效。 例一 Picture问题的概述 (选自IOI98) 例一 解题分析(1) 预处理： 如右图所示，用2n条横线与2n条纵线将坐标平面重新进行划分。定义新的坐标轴，并记录每一个“元线段”的长度。这样就只剩下了2n*2n个坐标点，便于今后的计算。 离散化，将2n条矩形的横边和2n条纵边取出来，分别计算 例一 解题分析(2) 做完预处理之后，如果直接计算，不难想到O(n2)的算法。 事实上，利用线段树我们可以设计出一个时间复杂度为O(nlogn)的高效算法。 在分析算法之前，我们先来看看线段树上插入和删除线段的操作。 例一 线段树的插入、删除(1) 增加一个Tree[i].Cover域，记录该区间（线段）被覆盖的次数。 则在线段树中插入线段[c,d]的代码段如下： 例一 线段树的插入、删除(2) 删除线段[c,d]的操作，只需要将Tree[v].Cover ← Tree[v].Cover + 1 改成 Tree[v].Cover ← Tree[v].Cover – 1 即可。 与引例中计算SUM的过程段类似地分析，不难得到线段树中插入和删除线段的时间复杂度都是O(logn) 例一 解题分析(3) 回到原问题，首先我们考虑纵向的离散区间。 例一 解题分析(4) 例一 解题分析(5) 例一 解题分析(6) 综合前面的分析，我们得到： 每次插入/删除