2014信息竞赛培训-高级数据结构

课前提醒希望

记好笔记我会画很多帮助理解的图，由于技术原因没有画在PPT上内容很散但是十分有用，注意回去继续理解区间询问经典的区间询问有：RMQ、GSS1让

先来看一下例子，寻找他们的共同点RMQRMQ：给数列a1,a2,..,an和若干询问(l,r)，回答区间最小值存在O(N

logN)预处理

O(logN)单次询问以及O(N

logN)预处理

O(1)单次询问GSS1GSS1：给数列a1,a2,..,an和若干询问(l,r)，回答区间[l,r]中最大连续和该利用什么性质？存哪些量？修改同时，区间询问又伴随着修改常见的修改有：单点修改、整段修改区间查询遇到的数据结构问题往往是区在竞赛中，间查询比较简单的情况是在一维的往往也可以变成树上的询问（不要怕，很多树上问题都可以变成一维的）关键的性质往往一个量好不好求，取决于它有哪些性质常用的性质有：交换律、结合律、求逆等等RMQRMQ：给数列a1,a2,..,an和若干询问(l,r)，回答区间最小值RMQ式是使用线段树，每个节点记录该区第间最小值段树的每个节点上，可以进行合并为什么可以这么做？因为结合律！RMQ在这里结合律的意思是，计算min这个函数，可以不按照从左到右的顺序min{a1,

a2,

...,

an}=

min{min{a1,

a2,

..,

a_i},

min{a_{i+1},

..,

an}}RMQ因此可以利用线段树分开计算，再合并这也是使用线段树最最基本的条件：计算结果可以拆分再合并（结合律）RMQ结合律只是一个最基本的性质min函数有更加强大性质使得可以做到O(1)单次询问RMQ发现：如果知道min{a1,a2,a3,a4}和min{a3,a4,a5,a6}就能算出min{a1,..,a6}也就是说

可以合并有交的区间RMQ因此，就容易得到O(N

logN)-O(1)的算法首先计算一个数组f[i][j]表示从第i个数开始，在区间[i,i+2^j-1]内的最小值f[i][j]可以通过f[i][j-1]和f[i+2^{j-1}][j-1]递推得到RMQ对于区间询问[l,r]首先得到一个k，2

*

2^k>=区间长度那么区间可以被两个2^k的区间覆盖，一个以l开头，一个以r结尾而这两个最小值 都已经存了起来，只要O(1)合并即可题外话为什么sum比min好求？由于sum好求逆，也就是说sum(l,r)=sum(1,r)-sum(1,

l-1)而对于min(l,

r)则没有这个性质因此求和往往很简单GSS1GSS1：给数列a1,a2,..,an和若干询问(l,r)，回答区间[l,r]中最大连续和该记录哪些区间询问，用线段树！量？GSS1考虑对于一个区间[l,r]，将其分为两个区间[l,m]和[m+1,

r]最大值可能产生于哪里？GSS1第一种情况是来自[l,m]或者[m+1,

r]之内，这种情况直接利用已经算好的信息即可否则会两个子区间，那么一定为[l,m]从右开始连续的最大和加上[m+1,r]从左开始连续的最大和GSS1再来看如何递推求从左开始的最大连续和、以及从右开始的最大连续和同样考虑将其分为两个区间[l,m]和[m+1,r]GSS1[l,r]从左开始连续最大和也有两种不

：则为[l,

m]

从左开始连续最大和：则为[l,m]的和加上[m+1,r]里从左开始连续最大和GSS1因此 只需要 四个量：区间和、从左最大连续和、从右最大连续和、区间内最大连续和询问也通过一样的方法合并请大家一定要写出这道题单点修改单点修改是线段是很容易做到的因为 最多会修改O(log

N)个区间例子：GSS1中加入把某个位置i取负做法：递归到最底层，然后自底向上更新区间修改线段树的区间修改往往稍难一些原因在于，如果

递推修改每个区间，要修改的区间会达到O(N)级别区间修改事实上，

不用递归到全部区间线段树的一个重要性质：每个区间都会被更大可以把原区间分解成O(logN)的区间覆盖，个区间利用懒标记！懒标记？区间修改拿一个例子来说，在GSS1中加入修改：把一个区间[l,r]的所有数都变成x做法：懒标记！简单来说，就是只修改当前需要的区间，不需要的之后再说。区间修改懒标记：lazy变量并不一定是bool型，可能会根据问题不同而不同，或者lazy本身就会有很多属性比如：在刚才的GSS1中加入区间操作，该怎么做？比较难的区间修改总的来说，区间修改基本都是通过懒标记完成不能用懒标记的情况，经过转换也能使用例如：NOI2012

魔幻棋盘一维魔幻棋盘给出一列数A[1],

A[2],..,A[n]，你需要支持下面两种操作：修改一个区间[l,r]，将每个值都加上c询问区间[l,r]的最大公约数一维魔幻棋盘如果没有修改，问题十分简单加入修改，懒标记似乎不work？是否可以进行适当的转化，使得懒标记适用？一维魔幻棋盘(a,

b)

=(a,

b

-

a)利用 的性质！那么：(a1,

a2,

..

an)

=(a1,

a2

-

a1,

..,

an

-

a{n-1})一维魔幻棋盘也就是说，每次求[l,

r]区间的

， 需要A[l]这个值，以及A[i]-A[i-1]的因此可以分开

A[i]的单值和A[i]

-

A[i-1]的区间

！A[i]

-

A[i-1]的区间

变成了单点修改一维魔幻棋盘A[l]：普通的线段树A[i]-A[i-1]：对于[l,r]加上c，相当于A[l]-A[l-1]加上c，A[r+1]-A[r]减去c分解为了两个单点修改一维版本解决，二维先跳过更进一步当修改不仅仅是单点/区间修改还有列入：在某个位置

、删除一个数例如：GSS1+、删除某个位置的数删除修改区间，几乎可以解决一法是用Splay维的所有问题如果可以请尽量采用这种方法是不是太复杂了？换个想法？离线？删除修改（或者被删除后），用一个占位符如果

能够预先留出位置给每个即将

的数在没有代替那么还是简单的区间问题其他数据结构二维线段树（一般都用树套树，更实用方便）其他数据结构平衡树，只需要知道