内容提要：
二叉搜索树
二叉堆
区间RMQ问题
二叉搜索树
前置技能
本节课可能用到的一些复杂度:
O(log n).
n/1+n/2+...+n/n=O(n log n)
入门题：
给出N次操作，每次加入一个数，删除一个之前加入过的数，或者询问当前所有数的最大值。
N ≤ 100000.
二叉搜索树
二叉搜索树(BST)是用有根二叉树来存储的一种数据结构，二叉树中每个节点代表一个数据。每个节点包含一个指向父亲的指针，和两个指向儿子的指
针。如果没有则为空。
每个节点还包含一个key值，代表他本身这个点的权值
特征：
二叉搜索树的key值是决定树形态的标准。
每个点的左子树中，节点的key值都小于这个点。
每个点的右子树中，节点的key值都大于这个点。
示例：
用结构体或者是若干个数组存储
在接下来的介绍中，我们将以ls[x]表示x的左儿子，rs[x]表示x的右儿子,fa[x]表示x的父亲，key[x]表示x这个点的权值。
BST是一种支持对权值进行查询的数据结构，它兹磁:
插入一个数，删除一个数，询问最大/最小值，询问第k大值。
当然，在所有操作结束后，它还能把剩下的数从小到大输出来
查询最大/最小值
注意到BST左边的值都比右边小，所以如果一个点有左儿子，就往左儿子走，否则这个点就是最小值啦。
代码(最小值)
int FindMin()
{
intx = root;
while (ls[x]) x = ls[x];
return key[x];
}
一直找左儿子
现在我们要插入一个权值为x的节点。
为了方便，我们插入的方式要能不改变之前整棵树的形态。
首先找到根，比较一下key[root]和x,如果key[root] < x,节点应该插在root右侧，否则再左侧。
看看root有没有右儿子，如果没有，那么直接把root的右儿子赋成x就完事了。
否则，为了不改变树的形态，我们要去右儿子所在的子树里继续这一操作，直到可以插入为止。
代码：
void insert(intval)
{
key[+ + tot] = val; ls[tot] = rs[tot] = ;
int now = root;//当前访问的节点为now.
for(; ; )
{
if (val < key[now])
if (!ls[now]) ls[now] = x, fa[x] = now, break;
else now =ls[now];
else if (!rs[now]) rs[now] = x, fa[x] =now, break;
else now = rs[now];
}
}
删除一个值
现在我们要删除一个权值为x的点
之前增加一个点我们能够不改变之前的形态，那删除可以吗?
定位一个节点
要删掉一个权值，首先要知道这个点在哪。
从root开始，像是插入一样找权值为x的点在哪
每次比较当前的key值和节点的大小关系，然后重复操作
代码：
int Find(int x)
{
int now = root;
while(key[now]! = x)
if (key[now] < x) now = rs[now]; else now = ls[now];
return now;
}
删除的方案：
方案一
直接把这个点赋成一种空的状态.但是这样的话查询起来不太方便（会有非常大的困难）。
所以还是稍微麻烦一点吧。
方案二
对这个节点x的儿子情况进行考虑。
如果x没有儿子，删掉x就行了。
如果x有一个儿子，直接把x的儿子接到x的父亲下面就行了。
这样子是肯定没有问题的，因为左边总比右边小嘛，所以x的儿子肯定比右边的大儿子小，这样就可以交换了
如果x有两个儿子，这种情况就比较麻烦了。
定义x的后继y，是x右子树中所有点里，权值最小的点。（有很多方法，这样比较方便，如果找左子树中最大的或者是直接删掉然后调整顺序应该也可以）
找这个点可以x先走一次右儿子，再不停走左儿子。
如果y是x的右儿子，那么直接把y的左儿子赋成原来x的左儿子，然后用y代替x的位置。
代码:
build2
先排序，从中间分开，两边生成的二叉搜索树接到中间的点上
求解第k大值(小扩展)
如果不能求的话它将会被堆完爆。
对每个节点在多记一个size[x]表示x这个节点子树里节点的个数（包含他自己）。
每个节点的size就是他的左右儿子的size之和+1
从根开始，如果右子树的size ≥ k,就说明第k大值在右侧，往右边走，如果右子树size + 1 = k,那么说明当前这个点就是第k大值。
否则，把k减去右子树size + 1,然后递归到左子树继续操作。
有相等的数据的话可以定义右边的为≥
插入或者删除的话他所有父亲的size都要+1或者-1
二叉搜索树也可以实现一个排序的作用
遍历
注意到权值在根的左右有明显的区分。.
做一次中序遍历就可以从小到大把所有树排好了。（左儿子--中节点--右儿子）
int dfs(int now)
{
if (ls[now]) dfs(ls[now]);
print(key[now]);
if (rs[now]) dfs(rs[now]);
}
回到最初的题
让我们回到最初的题。
一个良好的例子:3 1 2 4 5
一个糟糕的例子:1 2 3 4 5
二叉搜索树最坏的情况下每次操作访问O(h)个节点。(h为树高)
总结
既然他的复杂度与直接暴力删除类似，那我们为什么要学他呢?
1.因为教学安排里有(大误).
2.这是第一个能够利用树的中序遍历的性质的数据结构。
3.扩展性强。更复杂的splay,treap,SGT等都基于二叉搜索树，只是通过一些对树的形态的改变来保证操作的复杂度，且保持树中序遍历的形态。
4.因为数据很水。随机数据还是很强势的（树高期望是log n）
二叉堆
满 二叉树：除了最后一层节点其他都是满的，而且最后一层也是从左到右
每个节点的儿子是当前节点的序号*2和序号*2+1；
每个节点的父亲就是当前节点的序号/2
定义
用二叉搜索树还是没法解决我们之前的问题。
堆是一种特殊的二叉树，并且是一棵满二叉树。
第i个节点的父亲是i/2,这样我们就不用存每个点的父亲和儿子了。
二叉搜索树需要保持树的中序遍历不变，而堆则要保证每个点比两个儿子的权值都小。
建堆
首先是要建出这么一个堆，最快捷的方法就是直接O(N log N)排一下序。
反正堆的所有操作几乎都是O(log N)的。
之后可以对这个建堆进行优化。
求最小值
可以发现每个点都比两个儿子小，那么最小值显然就是a[1]辣，是不是很simple啊。
插入一个值
注意到二叉搜索树中的复杂度都是O(h).
在堆中我们也想让复杂度是O(h) = O(log n).
这样一来我们就要让树的形态不变，所以我们每次改变的都是权值的位置。
首先我们先把新加入的权值放入到n + 1的位置。
然后把这个权值一路往上比较，如果比父亲小就和父亲交换.
注意到堆的性质在任何一次交换中都满足。
修改一个点的权值
咦，为什么没有删除最小值?
删除最小值只要把一个权值改到无穷大就能解决辣
比较简单的是把一个权值变小，那只要把这个点像插入一样向上动就行了。
变大权值
那么这个点应该往子树方向走。
看看这个点的两个儿子哪个比较小，如果小的那个儿子的权值比他小，就交换，直到无法操作。
就是不断找到两个儿子中较小的一个进行交换
解决定位问题
一般来说，堆的写法不同，操作之后堆的形态不同，所以一般给的都是改变一个权值为多少的点.
假设权值两两不同，再记录一下某个权值现在哪个位置，在交换权值的时候顺便交换位置信息。
删除权值
理论上来说删除一个点的权值就只需要把这个点赋成inf 然后down一次。
但是这样堆里的元素只会越来越多（最后一层全是inf）
我们可以把堆里第n号元素跟这个元素交换一下。
然后n--,把堆down一下就行了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<set>
#include<vector>
#include<map>
#include<queue> #define N 300005
#define M 8000005 #define ls (t<<1)
#define rs ((t<<1)|1)
#define mid ((l+r)>>1) #define mk make_pair
#define pb push_back
#define fi first
#define se second using namespace std; int i,j,m,n,p,k,a[N]; int FindMin()
{
return a[];
} void build1()
{
sort(a+,a+n+);
} void up(int now)
{
while (now&&a[now]<a[now/]) swap(a[now],a[now/]),now/=;
} void ins(int x)
{
a[++n]=x; up(n);
} void down(int now)
{
while (now*<=n)
{
if (now*==n)
{
if (a[now]>a[now*]) swap(a[now],a[now*]),now*=;
}
else
{
if (a[now]<=a[now*]&&a[now]<=a[now*+]) break;
if (a[now*]<a[now*+]) swap(a[now],a[now*]),now*=;
else swap(a[now],a[now*+]),now=now*+;
}
}
} void del(int x)
{
swap(a[x],a[n]); --n;
up(x);
down(x);
} void change(int x,int val)
{
if (a[x]>val)
{
a[x]=val;
up(x);
}
else
{
a[x]=val;
down(x);
}
} void build2()
{
for (i=n/;i>=;--i) down(i);
} int main()
{
scanf("%d",&n);
for (i=;i<=n;++i) scanf("%d",&a[i]);
build2();
}
del那里可以比较两个大小再选择up或者down，也可以先up再down
建堆
现在来考虑一种新的建堆方法。
倒序把每个节点都down一下，正确性肯定没有问题。
复杂度n/2 + n/4 * 2 + n/8 * 3 + .... = O(n)
堆排序
给N个数，输出他们从小到大排序的结果.
N ≤ 100000.
题解：
把数全部插进去，每次询问最小值，然后把根删掉就行了.
复杂度O(N log N).
丑数
丑数指的是质因子中仅包含2, 3, 5, 7的数，最小的丑数是1,求前k个丑数。
K ≤ 6000.
题解：
打表大法好！没有什么是打表解决不了的.
算了说正经的。
考虑递增的来构造序列.
x被选中之后，接下来塞进去x * 2, x * 3, x * 5, x * 7.
如果当前最小的数和上一次选的一样，就跳过.
复杂度O(K log N).
Queue
每次都要写堆太麻烦了有没有什么方便的。
在C + +的include < queue >里有一个叫priority queue的东西。
基本操作
Q.push()
Q.top()
Q.pop()
Q.clear()
set
堆好弱小啊，有没有什么更好用的。
在C + +的include < set >里有一个叫set的东西。
高级的二叉搜索树
左闭右开
基本操作：
set<int>st
st.insert()//插入
st.erase()//删除
st.fnd()//查找
st.lower/upper bound()//第一个≥他的位置/第一个＞他的位置
st.begin()/st.end()//最大值/最小值后面的部分
有独有的迭代器
set<int>::iterator it=st.lower_bound(x);
++it;--it;//下标右移一位/左移一位
x=*it;//下表所对应的值
堆有啥用
我也不知道它有啥用(大雾
了解一种数据结构
为将来学习可并堆，斐波那契堆打下坚实基础(政治课即视
比STL快。
能优化dij(图论)
RMQ
区间RMQ问题是指这样一类问题。
给出一个长度为N的序列，我们会在区间上干的什么(比如单点加，区间加，区间覆盖),并且询问一些区间有关的信息(区间的和,区间的最大值)等。
最简单的问题
给出一个序列，每次询问区间最大值.
N ≤ 100000, Q ≤ 1000000
ST表
ST表是一种处理静态区间可重复计算问题的数据结构，一般也就求求最大最小值辣。
ST表的思想是先求出每个[i, i + 2k)的最值。
注意到这样区间的总数是O(N log N)的.
log N这一复杂度是OI最常用复杂度。
而sqrt(N)是OI最玄学的复杂度。
预处理
不妨令fi,j为[i, i + 2^j)的最小值。
那么首先fi,0的值都是它本身。
而fi,j = min(fi,j−1, fi+2^j−1,j−1)
这样在O(N log N)的时间内就处理好了整个ST表
ST表代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<set>
#include<vector>
#include<map>
#include<queue> #define N 300005
#define M 8000005
#define K 18 #define ls (t<<1)
#define rs ((t<<1)|1)
#define mid ((l+r)>>1) #define mk make_pair
#define pb push_back
#define fi first
#define se second using namespace std; int i,j,m,n,p,k,ST[K+][N],a[N],Log[N]; int Find(int l,int r)
{
int x=Log[r-l+];
return max(ST[x][l],ST[x][r-(<<x)+]); //注意到对于[l,r],[l,l+2^x-1],[r-2^x+1,r]并起来是[l,r]
} int main()
{
scanf("%d",&n);
for (i=;i<=n;++i) scanf("%d",&a[i]);
for (i=;i<=n;++i) ST[][i]=a[i];
for (i=;i<=K;++i)
for (j=;j+(<<i)-<=n;++j)
ST[i][j]=max(ST[i-][j],ST[i-][j+(<<(i-))]); //ST[i][j]为从j开始的长度为2^i的区间的最大值
//显然[j,j+2^i)=[j,j+2^(i-1))+[j+2^(i-1),j+2^i)=max(ST[i-1][j],ST[i-1][j+2^(i-1)])
for (i=;(<<i)<N;++i) Log[<<i]=i; //令Log[x]为比x小的最大的2^y
for (i=;i<N;++i) if (!Log[i]) Log[i]=Log[i-];
printf("%d\n",Find(,));
}
询问
比如我们要询问[l, r]这个区间的最小值.
找到最大的k满足2^k ≤ r − l + 1.
取[l, l + 2^k), [r − 2^k + 1, r + 1)这两个区间。
注意到这两个区间完全覆盖了[l, r],所以这两个区间最小值
较小的一个就是[l, r]的最小值。
注意到每次询问只要找区间就行了，所以复杂度是O(1).
注意
ST表确实是一个询问O(1)的数据结构，但是它的功效相对也较弱.
例如每次求一个区间的和，利用前缀可以做
到O(N) − O(1).而ST却无法完成。
做题四部曲：
比较简单的问题
给出一个序列，支持对某个点的权值修改，或者询问某个区间的最大值.
N, Q ≤ 100000
冷静分析
嗯，刚学了ST表
它只要O(1)就能询问了。
能不能让它动起来呢?
仔细思考
来考虑一下能不能强行维护ST表.
比如改5这个点.
j = 0 改了一个位置，嗯，完美.
j = 1 改了两个位置4, 5,稳.
j = 2 改了四个位置2, 3, 4, 5,还行.
...
发现问题
注意到当j往上走的时候，要改的区间的个数是这个点的编号.
现在修改一次要修改O(N)个点.
一看就很不靠谱
妈耶我凉了啊
ST表不靠谱，那怎么办呢
稍微考虑一下，可能是我们选的区间不靠谱。（因为会重叠）
换一种区间选取方式也许会靠谱。
线段树
其实线段树被称为区间树比较合适,本质是一棵不会改变形态的二叉树.
树上的每个节点对应于一个区间[a, b](也称线段),a,b通常为整数
他是维护区间的信息
基本形态
同一层的节点所代表的区间，相互不会重叠
同一层节点所代表的区间，加起来是个连续的区间
对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b](除法去尾取整）
叶子节点表示的区间长度为1.
示例1：n=10
示例2：n=9
注意到线段树的结构有点像分治结构,深度也是O(log N)的.
每层里面区间长度相差不超过一
区间拆分
区间拆分是线段树的核心操作,我们可以将一个区间[a, b]拆分成若干个节点,使得这些节点代表的区间加起来是[a, b],并且相互之间不重叠.
所有我们找到的这些节点就是”终止节点”.
区间拆分的步骤
从根节点[1, n]开始，考虑当前节点是[L, R].
如果[L, R]在[a, b]之内,那么它就是一个终止节点.
否则,分别考虑[L, Mid],[Mid + 1, R]与[a, b]是否有交,递归两
边继续找终止节点
区间拆分的例子
注意：
有多少个底层的点，至少需要开四倍
解题方法
充分利用区间分解的性质.
思考在终止节点要存什么信息,如何快速维护这些信息,不要每次一变就到最底层.
例1
给一个数的序列A1, A2, ..., An.并且可能多次进行下列两个操作：
1.对序列里面的某个数进行加减
2.询问这个序列里面任意一个连续的子序列Ai, Ai+1...Aj的和是多少.
希望单个操作能在O(log N)的时间内完成.
题解:
对于每个节点[L, R],我们记录AL + ... + AR.
对于操作1:相当于我们对[i, i]这个区间做了一个区间分解.沿路我们在找到[i,i]时经过的所有祖先节点.
对于操作2:我们对[L, R]做一个区间分解,将每个区间对应的和累加起来就是想要知道的区间和.
伪代码：
#include<cstdio>
#include<algorithm> #define N 100005 #define ls (t<<1)
#define rs ((t<<1)|1)
#define mid ((l+r)>>1) int tree[N*];
//操作1
void modify(int ll,int rr,int c,int l,int r,int t)//将t修改为c，并且进行更新
{
if (ll<=l&&r<=rr)
{
tree[t]=c;
return;
}
if (ll<=mid) modify(ll,rr,c,l,mid,ls);
if (rr>mid) modify(ll,rr,c,mid+,r,rs);
tree[t]=tree[ls]+tree[rs];
}
/*
void modify(int ll,int c,int r,int t)
{
if(l==r)
{
tree[t]=c;
return ;
}
if(ll<=mid) modify(ll,rr,c,l,mid,ls);
else modity(ll, rr,c,mid+1,r,rs);
tree[t]=tree[ls]+tree[rs];
} */
int S;
//操作2
void ask(int ll,int rr,int l,int r,int t)//[ll,rr]是要分解的区间 当前正分解到的节点编号是t,区间范围是[l,r]
{
if (ll<=l&&r<=rr)
{
S+=tree[t];
return;
}
if (ll<=mid) ask(ll,rr,l,mid,ls);
if (rr>mid) ask(ll,rr,mid+,r,rs);
} int main()
{
modify(l,l,c,,n,);
//相当于是从1~n对[l,l]这个区间进行区间分解
S=;
ask(l,r,,n,);
}
完整代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<set>
#include<vector>
#include<map>
#include<queue> #define N 300005
#define M 8000005 #define ls (t*2)
#define rs (t*2+1)
#define mid ((l+r)/2) #define mk make_pair
#define pb push_back
#define fi first
#define se second using namespace std; int i,j,m,n,p,k,add[N*],sum[N*],a[N],ans,x,c,l,r; void build(int l,int r,int t)
{
if (l==r) sum[t]=a[l];
else
{
build(l,mid,ls);
build(mid+,r,rs);
sum[t]=max(sum[ls],sum[rs]); //预先处理区间[l,r]的最大值
}
} void modify(int x,int c,int l,int r,int t) //将a[x]修改为c,然后需要对所有包含x的区间进行更新
{
if (l==r) sum[t]=c; //只有一个点的时候可以直接计算
else
{
if (l<=x&&x<=mid) modify(x,c,l,mid,ls);
else modify(x,c,mid+,r,rs);
sum[t]=max(sum[ls],sum[rs]);//回溯的时候[l,mid],[mid+1,r]的答案已经算出，可以利用两个儿子进行更新
}
} void ask(int ll,int rr,int l,int r,int t) //询问[ll,rr]这个区间的最大值,l,r,t表示的是当前线段树上位置代表的区间[l,r]和编号t
{
if (ll<=l&&r<=rr) ans=max(ans,sum[t]); //找到了一个完整被[ll,rr]区间包含的区间,直接把答案记进去
else
{
if (ll<=mid) ask(ll,rr,l,mid,ls); //如果和左儿子有交就往左儿子走
if (rr>mid) ask(ll,rr,mid+,r,rs); //如果和右儿子有交就往右儿子走
}
} int main()
{
scanf("%d",&n);
for (i=;i<=n;++i) scanf("%d",&a[i]);
build(,n,);
modify(,,,n,);
ask(,,,n,);
}
[POJ 3264]Balanced Lineup
给定Q个数A1, ..., AQ,多次询问,每次求某一区间[L, R]中最大值和最小值的差.
Q ≤ 50000
Sol
改存每个区间中的最大最小值,然后更新的时候注意要从左儿子和右儿子处更新过来
（就是min和max）