高度由习惯堆积

分类 数据结构:主席树 下的文章

January 10, 2019

主席树模板

概念主席树,又名可持久化线段树,是解决区间第k大问题的利器。其原理是运用函数化思想,在每一个点上都构建一课[1,i]的线段树,线段树中存的是数值而不是下标。基本思想我们先思考一个会MLE&TLE的解法:对于每个点,构建一棵[1,i]线段树,存放[1,i]的所有$A[i]$,比如说前三个数为1,3,2,则这棵线段树如下图: