线段树讲解

ACM算法与程序设计结课论文1关于线段树数据结构的研究线段树（SegmentTree）是一种高级的数据结构，顾名思义，它既是线段也是树，并且是一棵二叉树。线段树的每个节点是一条线段[a,b],每条线段的左右儿子线段分别是该线段的左半区间[a,(a+b)/2]和右半区间[(a+b)/2+1,b]，递归定义之后就是一棵线段树。因此，线段树是平衡二叉树，且最后的叶子节点数为N，即整个线段区间的长度。要知道，在不同的题目中，线段可以有不同的含义，如数轴上的一条真实的线段，或者是一个序列的连续子序列。使用线段树可以快速地查找某一节点在若干条线段中出现的次数，时间复杂度是O(logN)。图示如下：[1,8]/\[1,4][5,8]/\/\[1,2][3,4][5,6][7,8]/\/\/\/\[1,1][2,2][3,3][4,4][5,5][6,6][7,7][8,8]线段树有以下操作：⑴区间查询询问某段区间的某些性质（极值，求和）⑵区间更新某些操作影响了某段区间（统一加了一个值）⑶三个问题①更新点，查询区间②更新区间，查询点③更新区间，查询区间ACM算法与程序设计结课论文2定义线段树的数据结构Structtree{Intleft,right;//区间的端点Intmax,sum;//视题目要求而定，重点维护的信息}tree[N*4];//线段树空间应为原数组长度的4倍我们用一个一维的结构体数组tree[N*4]来记录节点，且根节点的下标为1，则对于任意非叶子节点tree[k]，它的左二子为tree[2*k]，它的右儿子为tree[2*k+1].线段树的代码实现（建树）Voidbuild(intid,intl,intr){Tree[id],left=l;Tree[id].right=r;If(l==r)Tree[id].sum=l;Tree[id].max=l;Else{Intmid=(l+r)/2;Build(id*2,l,r);Build(id*2+1,l,r);Tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;Tree[id].max=max(tree[id*2].max,tree[id*2+1].max);}}//如果原数组从a[1]~a[n]，调用build(1,1,n)即可线段树的点更新Voidupdate(intid,intpos,intval){If(tree[id].left==tree[id].right)Tree[id].sum=val;Else{ACM算法与程序设计结课论文3Intmid=(tree[id].left+tree[id].right)/2;If(pos=mid)Update(id*2,pos,val);ElseUpdate(id*2+1,pos,val);Tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;}}线段树的查询intquery(intid,intl,intr){if(tree[id].left==l&&tree[id].right==r)returntree[id].sum;else{intmid=(tree[id].left+tree[id].right)/2;if(r=mid)returnquery(id*2,l,r);//待查区间在其左子区间中elseif(lmid)returnquery(id*2+1,l,r);//待查区间在其右子区间中elsereturnquery(id*2,l,mid)+query(id*2+1,mid+1,r);//待查区间横跨其左右子区间}}很多时候，将问题建模成数轴上的问题或是数列上的问题后，具体地操作一般是每次对数轴上的一个区间或是数列中的连续若干个数进行一种相同的处理，比如统一加上一个数，如果处理只针对各个元素逐个进行，导致算法的效率较低。解决的方案是lazy思想：对整个节点进行操作，先是在节点上做标记，而非真正执行，直到根据查询操作的需要分成两部分。根据lazy思想，我们可以再节点上增加一个值lazy，即对这个节点留待以后执行的插入操作k值的总和。对整个节点插入时，只更新lazy和sum的值而不向下进行。对一个lazy值为0的节点整个查询时，直接返回存储在其中的sum值，而若对lazy不为零的一部分进行查询时，则要更新其左右子节点的sum值，然后把lazy的值传递下ACM算法与程序设计结课论文4去，在对这个本身查询，左右子节点分别递归下去。值得注意的是，lazy标记表示的是这段区间以下的所有子区间将要进行的操作，并不包括当前的区间，即当前的区间已经更新完毕。从中我们可以看出这个lazy标记不仅仅是作用于某一个节点，而是作用于整个子树的。接下来我们通过几道典型例题来具体的体会线段树的用法。（以下两题均选自ACM校集训队讲座的题目）【母仪天下】富庶的建业城中，有一条格格不入的长街，名曰跳蚤街，被战争所致的孤儿，聚集于此。全国的经济都在为战争服务之时，也无人顾得了这里了。除了两位夫人。大乔小乔每天都会带着一些食物来到跳蚤街，分给某一位孩子。为了避免分配不均，她们时常会询问一个区域内食物的总量，然后进行调整以保证每个孩子都有足够的食物。Input第一行两个整数n，m，表示跳蚤街住着n户孩子，大乔小乔一共分发或询问了m次。第二行n个整数，第i个数ai表示第i户孩子已有ai的食物。接下来m行，每行开始先读入一个整数si，指明这是一次询问还是一次分发。si=0，表明这是一次询问，然后读入两个整数li,ri，表示询问[li，ri]区间中的孩子们一共有多少食物。si=1，表明这是一次分发，然后读入两个整数xi,wi，表示对第xi户孩子分发了wi的食物。1≤n,m≤100000,0≤ai≤100000,1≤xi≤n,0≤wi≤10000,1≤li≤ri≤nOutput有多少询问就输出多少行，每行输出一个整数，作为对该询问的回答。“母仪天下”这道题属于线段树的简单应用，根据题意，首先要读入数据并建立线段树数据结构，然后再根据读入s的值执行不同的操作。如果s=1，则要将此叶子ACM算法与程序设计结课论文5节点加上一个值，调用函数update（）；如果s=0，则要查询此叶子节点，调用函数query（）。以下是完整的代码：#includestdio.h#includestdlib.h#defineLEN100000structTree{intleft,right;intsum;};structTreetree[LEN*4];voidbuild(intid,intl,intr){tree[id].left=l;tree[id].right=r;if(l==r){return;}else{intmid=(l+r)/2;build(id*2,l,mid);build(id*2+1,mid+1,r);}}voidupdate(intid,intpos,intval){if(tree[id].left==tree[id].right){tree[id].sum=val;}else{intmid=(tree[id].left+tree[id].right)/2;if(pos=mid)update(id*2,pos,val);elseupdate(id*2+1,pos,val);tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;}}intquery(intid,intl,intr)ACM算法与程序设计结课论文6{if(tree[id].left==l&&tree[id].right==r)returntree[id].sum;else{intmid=(tree[id].left+tree[id].right)/2;if(r=mid)returnquery(id*2,l,r);elseif(lmid)returnquery(id*2+1,l,r);elsereturnquery(id*2,l,mid)+query(id*2+1,mid+1,r);}}intmain(){intn,m,a,i,s,x,y;scanf(%d%d,&n,&m);build(1,1,n);for(i=1;i=n;i++){scanf(%d,&a);update(1,i,a);}for(i=1;i=m;i++){scanf(%d%d%d,&s,&x,&y);if(s){update(1,x,y+query(1,x,x));}else{printf(%d\n,query(1,x,y));}}return0;}【东风不与周郎便】“揽二乔于东南兮，乐朝夕之与共”一首铜雀台赋，将愤怒与恐惧散播在了孙吴大军之中。对抗曹军，万事俱备，只欠东风。ACM算法与程序设计结课论文7现在已经找到n个风眼，这些风眼的东风有强有弱，诸葛亮说他每次祈风都能够将一段风眼的东风增强，但需人去帮他布阵。同时他需要时刻掌控风眼的状况，以确定下一步的计划，所以还需要知道一段风眼的强度之和。借东风，此乃逆天之术，施术者会折阳寿不说，布阵者更是会受十倍之伤。“何人能当此任？”“在下愿往，大都督。”“你是？”“在下一无名小卒，来自跳蚤街。”Input第一行两个整数n，m，表示有n个风眼，诸葛亮一共祈风或询问了m次。第二行n个整数，第i个数ai表示第i个风眼已有东风的强度。接下来m行，每行开始先读入一个整数si，指明这是一次询问还是一次祈风。si=0，表明这是一次询问，然后读入两个整数li,ri，表示询问[li，ri]区间中风眼的东风强度之和。si=1，表明这是一次祈风，然后读入三个整数li,ri,wi，表示把[li，ri]区间中每个风眼的东风强度提升wi。1≤n,m≤100000,0≤ai≤10000,0≤wi≤10000,1≤li≤ri≤nOutput有多少询问就输出多少行，每行输出一个整数，作为对该询问的回答。从题目描述中可以看出“东风不与周郎便”这道题和“母仪天下”不同，属于线段树的区间查询与区间更新问题，需要用到lazy标记。同样，我们首先要读取数据并建树，然后根据s的值的不同执行不同的操作。如果s值为1，则更新区间，调用update函数；如果s值为0，则查询区间调用query函数，并输出查询的结果。此题的关键是lazy标记的运用。ACM算法与程序设计结课论文8以下是完整的代码：#includestdio.h#includestdlib.h#includestring.h#defineLEN100000structTree{intleft,right;longlongintsum;longlongintup;};structTreetree[LEN*4];voidbuild(intid,intl,intr){tree[id].left=l;tree[id].right=r;tree[id].up=0;tree[id].sum=0;if(l==r){return;}else{intmid=(l+r)/2;build(id*2,l,mid);build(id*2+1,mid+1,r);return;}}voidupdate(intid,intl,intr,longlongintup){if(tree[id].left==l&&tree[id].right==r){tree[id].up+=up;return;}else{tree[id].sum+=(r-l+1)*up;intmid=(tree[id].left+tree[id].right)/2;if(r=mid)update(id*2,l,r,up);elseif(lmid)update(id*2+1,l,r,up);else{update(id*2,l,mid,up);update(id*2+1,mid+1,r,up);}ACM算法与程序设计结课论文9return;}}longlongintquery(intid,intl,int