WC2011-线段树-曹钦翔.ppt

线段树 北京大学哲学系 曹钦翔 目录 1.模块化编程 2.从线段树高级功能到线段树结构的设计 3.从OI问题到线段树功能的设计 1.1 线段树基本问题 有一个长为n的数列（输入），维护m次操作，每次操作是以下两种之一： (1)修改数列中的一个数 (2)求数列中某连续一段的最小值 解决思路：存储不变化的整体信息减少冗余操作 1.2 线段树的结构 n=8的结构： 结构要点 根节点为：min[1] 总层数h为O(logn)的 min[k]的左右儿子：min[2k]、min[2k+1] min[k]的父节点：min[k/2] a[k]对应的叶子节点：min[k+2h-1] 单点修改操作 段查询操作 1.3 段修改操作的问题 有一个长为n的数列（输入）a[1],a[2]…a[n]，有m次操作，每次操作是以下两种之一： (1)将数列中的一段a[l]…a[r]全部改成常数C (2)询问某一项a[i]当前的值 段修改的应对：整体修改标签 单点查询操作 段修改操作 Step 1: 快速查找叶子节点 Step 2: 开区间代替闭区间 Step 3: 自顶向下传递整体修改信息 Step 4: 自底向上添加整体修改信息 Step 5: 自底向上从新统计统计信息 段查询操作2 Step 1: 快速查找叶子节点 Step 2: 开区间代替闭区间 Step 3: 自顶向下传递整体修改信息 Step 4: 自底向上统计答案 1.5 模式化的程序 Step 1: 快速查找叶子节点 Step 2: 开区间代替闭区间（限于段操作） Step 3: 自顶向下传递整体修改信息 Step 4: 自底向上统计（段查询）/修改（段修改） 1.5 模式化的程序 2. 线段树结构的设计 模式化之外的部分： 1. Saving Data的设计 例题 2.1 问题描述 有一个平面连轴支架，包含n根棍子，相邻两根有一个连接点。第一根有一端（不连第二根的那端）固定在(0,0)。维护三个操作： (1)绕某一连接点旋转（这个点把所有棍子分成两部分，他们旋转时分别是一个整体） (2)某根棍子拉长或缩短 (3)询问某连接点坐标 例题 2.2 问题描述 有一个集合A，初始值时，维护以下操作： (1)与某区间取并 (2)与某区间取交 (3)与某区间取对称差 (4)减去某区间 例题 2.2 问题描述 (5)被某区间减 (6)取补 (7)询问某数是否在该集合内 在程序最后，以区间的并的形式输出该集合 例题 2.3 问题描述 输入一个长为n的数列，维护m个操作，操作分为三类： (1)某连续段一起加上一个常数 (2)询问某一段的所有数的两两乘积的和 (3)询问某一段的所有相邻两数乘积的和 例题 2.4 问题描述 输入两个个长为n的数列a[i],b[i]，维护m个操作，操作分为三类： (1)对于某一连续段将其中的b[i]加到a[i]上 (2)对于某一连续段将其中的a[i]加到b[i]上 (3)询问某一段中所有的a[i]b[i]的和 例题 2.5 问题描述 输入长度为n的数列a[i]。维护m次操作，每次操作可以： (1)a[l]…a[r]每一项都加一个常数C (2)求F[ a[l] ]+F[ a[l]+1 ]+…F[ a[r] ]mod 10001的余数 (3)求F[ a[l] ]+F[ a[l+1] ]+…F[ a[r] ]mod 10001的余数 其中F[i]表示斐波那契数列。即F[0]=F[1]=1，F[n+2]=F[n+1]+F[n]。（C=10^11） 例题 2.6 问题描述 输入一个状态集大小不超过10的AC自动机，s是一个字符串，即AC自动机的输入。维护m个操作，操作分为两类： (1)修改s的一个字符 (2)询问s对应的输出 例题 2.7 问题描述 平面上放置了一个正四面体，初始时底面是A面，且此时A面中心在原点，“向前”方向为Y轴正方向。可以对该四面体执行指令左转（L）、右转（R）、后转（B）。s是一个输入的指令串。维护m个操作，操作分为三类： (1)修改s的一个字符 (2)询问s执行结束后，地面中心距离原点的距离 (3)询问某段时间内，A成为底面的次数 例题 2.7 例题 2.8 问题描述 有一个2*n的点阵，平行于坐标轴的方向上相邻的点之间可以连边，维护以下操作： (1)在某两点之间连边（可以连边的话） (2)拆除某条边 (3)询问某两点是否连通 例题 2.8 例题 2.9 问题描述 白雪公主和n个小矮人住在森林里，当小矮人们排成一排向外走的时候，每个人头上都戴了一顶帽子，每顶帽子有一种颜色。这时候白雪公主给他们拍照片，共拍了m张，每张照片包括了队伍中连续的几个小矮人。 白雪公主认为，如果一张照片中某种颜色的帽子超