骞平衡树信息学奥林匹克

1、目摘关键正目摘关键正四、结束参考文2平平这一类数据结构进行归纳和总结 平平平这一类数据结构进行归纳和总结 平的很简3一、平的定义平平：线：4一、平的定义平平：线：4静静态与动态的比较。5静静态与动态的比较。51。2。区间信方不儿子节点，根据修改直接更新当前节点的区间信息关于这个1。2。区间信方不儿子节点，根据修改直接更新当前节点的区间信息关于这个区间的整体修改过的信息 6方式ab7方式ab7二、平的实现儿子节点的区间信息，还儿子节点的标记信息两种常用操12伪代Void 处理（节点 If二、平的实现儿子节点的区间信息，还儿子节点的标记信息两种常用操12伪代Void 处理（节点 Ifttt8处理（

2、t处理（tt9处理（t处理（tt9静态二叉搜索树又叫虚二叉树。关于虚二叉树的详细介绍，请看参考文献9介绍，请看参考文献6、7、8、9：考文献8区间信息和标记信息静态二叉搜索树又叫虚二叉树。关于虚二叉树的详细介绍，请看参考文献9介绍，请看参考文献6、7、8、9：考文献8区间信息和标记信息logn平衡二叉方式有多种方法AVL、Treap1SBT2关于伸展树的详细介绍，请看参考文献3、5SBT2关于伸展树的详细介绍，请看参考文献3、5三、平的应用1题目大意算法分析到三、平的应用1题目大意算法分析到AC2郁闷的出纳员题目大意IkASFk算法分析把每位员工的工资加上kk1，kO(logn)3 Key题目

3、SFk算法分析把每位员工的工资加上kk1，kO(logn)3 Key题目大意If （aL为空） 算法分析。：树4 题目大意Move INSERT(n, Insert 树4 题目大意Move INSERT(n, Insert S在光标长度为n的字符串s，光标位置不变n Delete n个字符，光标位置不变，n Get n个字符，光标位置不变，n 算法分析字符MOVE、PREV、NEXT操作只一下光标的位置INSERT、DELETEGET其例14算法分析字符MOVE、PREV、NEXT操作只一下光标的位置INSERT、DELETEGET其例141k2kk=1，k=5 题目大意光标前个字光标后个字算

4、法分析6 ASimpleProblem 题目大意一个序列：A1，A2，A3，An1k算法分析6 ASimpleProblem 题目大意一个序列：A1，A2，A3，An1k2算法分析没完7 Mobilephones题目大意算法分析没完7 Mobilephones题目大意算法分析：8形和（7强版题目大意18形和（7强版题目大意12、算法分析平logn*logn，9链工厂题目大意9链工厂题目大意N1,2,c 中的一种. . ,N算法分析区间信息：当前区间由多少个“部分”组成由于更新的时候，除了要知道左右儿子节算法分析区间信息：当前区间由多少个“部分”组成由于更新的时候，除了要知道左右儿子节点的区间由多少个“部分”组成，还小20032008NOI，都考查了平08不难想到要用。同时这也说明掌握好10 Dynamic题目大意一个序列：A1，A2，A3，An1Ak2Ai，Ai+1，Ajk算法分析kk，k具体细节请看参考文献4311000000000小k具体细节请看参考文献4311000000000小四、结束语平参考文刚，IOI2005矛，IOI2004，IOI2002睿，IOI2002Size Balanced Tree黄林薛李致感谢CCF四、结束语平