区间第k小值 主席树是解决动态查找序列上[l,r]区间中的第k小值的一个数据结构 核心思想:动态开点（后面会讲）传统线段树都是值域线段树其实意思就是每个节点都存的是序列上[l,r]的一个区间和，但是考虑我们需要动态处理区间的不是最值，故换一种线段树 主席树一般用的是权值线段树就是把[l,r]改为[min(a),max(a)]a是序列A在[l,r]区间里的一个子序列，每个节点下都保存一个统计数字s,代表在当前权值域里，有多少个数字array:1433 [1,4] s=4 [1,2][3,4] s=1s=3 [1,1][2,2][3,3][4,4] s=1s=0s=2s=1   &n...

splay简要讲解 前置芝士:普通二叉树 splaytree是一个越处理越灵活的数据结构,通过splay(伸展)操作,使整棵树的单次查询时间复杂度接近于O(logn),整棵树的高度也接近于logn 根据上面的这句话,很明显能看出splay与普通二叉树的区别 普通二叉树经过多次处理后,很容易退化成链,单次查询的复杂度直升O(n),对于处理大型数据来说,这是绝对不能允许的 OI和ACM界也经常会有数据能使一个普通二叉树快速退化成链 例: 123456789   很明显,对于大型数据的处理来说,普通二叉树已经满足不了了   下面,我将会以例图来讲解中序遍历 这张图是我...