内容提要：
二叉搜索树
二叉堆
区间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] = 0; 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#include #include #include #include #include #include #include #include #include #include
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 stst.insert()//插入st.erase()//删除st.fnd()//查找st.lower/upper bound()//第一个≥他的位置/第一个＞他的位置st.begin()/st.end()//最大值/最小值后面的部分有独有的迭代器set ::iterator it=st.lower_bound(x);++it;--it;//下标右移一位/左移一位x=*it;//下表所对应的值
堆有啥用
我也不知道它有啥用(大雾了解一种数据结构为将来学习可并堆，斐波那契堆打下坚实基础(政治课即视比STL快。能优化RMQ
区间RMQ问题是指这样一类问题。给出一个长度为N的序列，我们会在区间上干的什么(比如单点加，区间加，区间覆盖),并且询问一些区间有关的信息(区间的和,区间的最大值)等。 最简单的问题给出一个序列，每次询问区间最大值.N ≤ 100000, Q ≤ 1000000ST表
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#include #include #include #include #include #include #include #include #include #include
询问
比如我们要询问[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#include #define N 100005#define ls (t<<1)#define rs ((t<<1)|1)#define mid ((l+r)>>1)int tree[N*4];//操作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+1,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+1,r,rs);}int main(){ modify(l,l,c,1,n,1); //相当于是从1~n对[l,l]这个区间进行区间分解 S=0; ask(l,r,1,n,1);}
完整代码
#include#include #include #include #include #include #include #include #include #include #include
[POJ 3264]Balanced Lineup
给定Q个数A1, ..., AQ,多次询问,每次求某一区间[L, R]中最大值和最小值的差.Q ≤ 50000Sol
改存每个区间中的最大最小值,然后更新的时候注意要从左儿子和右儿子处更新过来（就是min和max）