线段树(课件)

1、线段树 -buctears线段树 n在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在X轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。在这类问题中，线段树的一个节点表示一段线段。n还有另外一类问题，线段树的每个节点表示一个点，称为点树，比如用于求第K小数的线段树。线段树的构造思想 n线段树是一棵二叉树，树中的每一个结点表示了一个区间a,b。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点a,b，其左儿子表示的区间为a,(a+b)/

2、2，右儿子表示的区间为(a+b)/2+1,b。 线段树的模型线段树的运用n线段树的每个节点上往往都增加了一些其他的域。在这些域中保存了某种动态维护的信息，视不同情况而定。这些域使得线段树具有极大的灵活性，可以适应不同的需求。例1n桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？WallLight分析n这道题目是一个经典的模型。在这里，我们略去某些处理的步骤，直接分析重点问题，可以把题目抽象地描述如下：x轴上有若干条线段，求线段覆盖的总长度。Sum=?最直接的做法n设线段坐标范围为min,max。使用一

3、个下标范围为min,max-1的一维数组，其中数组的第i个元素表示i,i+1的区间。数组元素初始化全部为0。n对于每一条区间为a,b的线段，将a,b内所有对应的数组元素均设为1。最后统计数组中1的个数即可。示例n初始情况n1，2n3，5n4，6n5，600000101101000010111101114个1缺点n此方法的时间复杂度决定于下标范围的平方。n当下标范围很大时（0,100000），此方法效率太低。n那应该如何做？n当然是本课要讲的-线段树n如何实现呢？线段树的数据结构表示n1. 动态数据结构n2. 完全二叉树1. 动态数据结构n指针nStruct noden node * left;

4、n node * right;n n2. 完全二叉树n静态全局数组模拟nstruct Noden int left, right;n nnodeMAXN*4n一般大小开成节点数的4倍，不需要担心空间问题线段树的题目分类n可分为以下四大类：1、单点更新:最最基础的线段树,只更新叶子节点,然后回溯更新其父亲结点2、成段更新:(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候3、区间合并 这类题目会询问区间中满足条件的连续最长区间,所以回溯的时候需要对左右儿子的区间进行合并4、扫描线：这类题

5、目需要将一些操作排序,然后从左到右用一根扫描线(当然是在我们脑子里)扫过去最典型的就是矩形面积并,周长并等题n每个分类都有对应的题目n课下练习 nhttp:/ Build）n2、更新操作（Update）n3、查询操作（Query）n4、向上回溯（Pushup）n5、向下延时更新（Pushdown）一般就这5个函数，可谓是模板化建树 Buildvoid Build (int u,int left,int right)/u表当前结点 /left right 表左区间范围left,right nodeu.l = left,nodeu.r = right; . /结点信息的初始化 if (nodeu.

6、l = nodeu.r) /到叶结点 return /某些赋值 return ; int mid = (nodeu.l + nodeu.r)1; Build (L(u),left,mid); Build (R(u),mid+1,right);更新操作 Updatevoid Update(int u,int left,int right,data val) if (left=nodeu.l&nodeu.r 1; /然后就是往左 往右 或左右找区间 几乎所有的 if (right mid) Update(R(u),left,right,val); else Update(L(u),left

7、,mid,val); Update(R(u),mid+1,right,val); Pushup(u); /这里也一般有个向上更新查询操作 QuerynData Query(int u,int left,int right) if (left = nodeu.l&nodeu.r 1; if (right mid) return Query(R(u),left,right); else return (Query(L(u),left,mid) + Query(R(u),mid+1,right); Pushup(u); /向上回溯 Pushup该函数就是由子结点递归回来 修改父结点中的信息v

8、oid Pushup(int u) nodeu.sum = nodeL(u).sum + nodeR(u).sum; . . return ;延时更新 Pushdown调用此函数时，结点中一般有个状态标志位 用来判断是否需要往下更新void Pushdown (int u) /延迟覆盖操作 if (nodeu.state = -1) 更新父结点，左右子结点信息 else if (nodeu.state = 1) 更新父结点，左右子结点信息 else 例题：A Simple Problem with IntegersPoj 3468:/problem?id=3468题意

9、：在一组数中执行两种操作C a b c means adding c to each of Aa, Aa+1, . , Ab. -10000 c 10000.Q a b means querying the sum of Aa, Aa+1, . , Ab.思路：如果每次更新都更新到底，会TLE（可以尝试一下）归属于区间更新 当更新某一段时，记录其状态，不再往下更新，直到下次更新或查询它的子结点时，再往下更新。附代码（自行研究）#include #include #define L(u) (u1)#define R(u) (u1|1)#define LL long longconst int M

10、 = 100005;struct Node int l,r; LL add,sum;nodeM1; Build (L(u),left,mid); Build (R(u),mid+1,right); Pushup(u);void Update(int u,int left,int right,LL val) if (left=nodeu.l&nodeu.r 1; if (right mid) Update(R(u),left,right,val); else Update(L(u),left,mid,val); Update(R(u),mid+1,right,val); / Pushup

11、(u); /这里不需要再向上更新，因为我们是从上到下更新的LL Query(int u,int left,int right) if (left = nodeu.l&nodeu.r 1; if (right mid) return Query(R(u),left,right); else return (Query(L(u),left,mid) + Query(R(u),mid+1,right); /Pushup(u);int main () #ifdef LOCAL freopen(in.txt,r,stdin); #endif int n,m,i,a,b; LL c; char c

12、h3; while (scanf (%d %d,&n,&m) for (i = 1;i = n;i +) scanf (%lld,&Ai); Build(1,1,n); while (m -) scanf (%s,ch); if (ch0 = Q) scanf (%d%d,&a,&b); printf (%lldn,Query(1,a,b); else scanf (%d %d %lld,&a,&b,&c); Update(1,a,b,c); return 0;关于离散化什么是离散化？我现在对他的初步理解是 因为给的范围无限大或过大无法用数组直接表示，所以进行转换。线段数的题中，有时候进行离散化处理，原因一是范围太大，无法用数组保存，二是，会超时。如开篇那题当下标范围很大时（0,100000），但题目有个条件说线段数不超过 1000时，离散化后点数就成2000而已。如何离散比如说有以下区间范围1,6 1.7 2,10 8 18 将各点排序1 1 2 6 7 8 10 18 离散后对应的坐标为 1 2 3 4 5 6 7 再根据原来的点把它们对应起来，则离散后坐标为1,3 1,4 2,6 5,7如何实现？观察上面