资源描述：
《信息学奥数NOIP线段树与树状数组ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、线段树与树状数组1前言OI中有三个极为重要的用于维护序列的数据结构：线段树、树状数组、平衡树，其中前两者使用在NOIP中的可能性更大前两者相比，线段树更易于理解，功能更强大，灵活、变化多端；树状数组功能较少，但是拥有代码简易、常数小的优势鉴于线段树更易理解且功能更强大，所以我们先讲线段树2基本问题线段树先给出一个最基本的线段树可解决的问题：给定一个长度为n的整数序列A[1..n]，有以下两种操作：1、使A[x]加上y2、求A[x..y]的和通常n≤100000，操作次数n≤1000003简单概念线段树接下来介绍一下什
2、么是线段树(前置知识：二叉树)线段树是一棵二叉树，每个节点表示序列上的一段区间，其中根节点表示区间[1,n]从根节点开始，只要区间长度不为1，就将区间划分为两半，并分给两个子节点4简单概念线段树例如以下是一个n=8时的线段树：当节点表示区间[l,r]，当l≠r时，左孩子表示[l,(l+r)/2]，右孩子表示[(l+r)/2+1,r]当l=r时，该节点为叶子节点[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][1,8]
3、[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]基本性质线段树序列长为n的线段树有三个比较基本的性质：1、总节点数为2n-12、层数约为log2n，即每个叶节点到根节点的距离约为log2n3、任何区间都可以用不超过2log2n个节点组合而成我们先不考虑线段树的代码实现，先以基本问题为例，研究一下它的工作原理我们先在线段树的每个节点都储存该区间的总和。假设起始都为0[1,8]0[1,4]0[5,8]0[1,2]0[3,4]0[5
4、,6]0[7,8]0[1]0[2]0[3]0[4]0[5]0[6]0[7]0[8]0算法介绍线段树-原理对于操作1，令A[x]加上y，我们先从根节点出发，找到[x,x]，比如x=3此时，路径上每个区间都包含x接下来，将这些区间储存的总和都加上y，比如y=4[1,8]0[1,4]0[5,8]0[1,2]0[3,4]0[5,6]0[7,8]0[1]0[2]0[3]0[4]0[5]0[6]0[7]0[8]0算法介绍线段树-原理[1,8]4[1,4]4[5,8]0[1,2]0[3,4]4[5,6]0[7,8]0[1]0[2]
5、0[3]4[4]0[5]0[6]0[7]0[8]0同上述操作步骤，一下是执行过：A[3]+=4，A[1]+=2，A[7]+=3后的结果[1,8]9[1,4]6[5,8]3[1,2]2[3,4]4[5,6]0[7,8]3[1]2[2]0[3]4[4]0[5]0[6]0[7]3[8]0算法介绍线段树-原理接下来询问区间[x,y]的总和先将[x,y]在线段树上用不超过2log2n个节点表示出来怎么表示？以[2,7]为例之后这些区间的总和就是答案(0+4+0+3=7)[1,8]9[1,4]6[5,8]3[1,2]2[3,4]
6、4[5,6]0[7,8]3[1]2[2]0[3]4[4]0[5]0[6]0[7]3[8]0算法介绍线段树-原理算法介绍线段树-实现-存储在理解了线段树的工作原理之后，开始考虑其代码实现首先是线段树的储存为了储存线段树，我们需要给每个节点一个编号。编号方式通常有两种：i*2和i*2+1作i的孩子；按构建顺序编号。此处主要介绍按构建顺序编号的方法，这也有利于以后动态开点线段树的学习算法介绍线段树-实现-存储存储也有两种方式：多个数组；struct数组个人习惯struct数组，所以以struct数组为例lc,rc分别为左右
7、孩子的编号，sum为该区间的总和。数组大小为序列长度两倍至于区间的左右端点[l,r]，可以存储，也可以递归时计算。个人习惯不存储，节省空间算法介绍线段树-实现-构建构建过程递归实现，voidbuild(intu,intl,intr)u为当前点编号，l,r为区间端点从根节点开始构建，递归时计算并代入l,r若l=r，该点为叶子节点，令sum=序列原值否则，递归构建左右孩子，之后令sum=左孩子sum+右孩子sum算法介绍线段树-实现-构建在主程序中：t=1;build(1,1,n);即可算法介绍线段树-实现-单点修改修改
8、过程递归实现voidupdate(intu,intl,intr,intx,intw)X为要修改的位置，w为变化量从根节点开始修改若当前点为叶子节点，使sum+=w并返回否则判断x在左孩子还是右孩子，递归进行修改，之后令sum=左孩子sum+右孩子sum算法介绍线段树-实现-单点修改在主程序中调用update(1,1,n,x,y);算法介绍线段树
