【主席树】HDU2665 Kth number

(昨天)【毛主席生日学会主席树】233

先说明一下,主席树其实叫Persistent Tree,意为可持久化线段树/函数式线段树,因为persistent长得有点像president,主席读起来比较上口,于是就叫主席树了XD。

这个也是入门题,轻松A掉XD

题意:给定n个数字,m个询问,每次求[L,R]内的第k大值

用线段树只能求最大,所以要用可持久化的线段树维护

具体的话。。做了个课件准备寒假讲的,直接看吧233

主席树课件

然后是代码:

(update:发现build函数并没有什么卵用于是去掉了,root[0]始终为0就行了,l[0]、r[0]和val[0]也都是0所以就相当于空树;这样省了时间省了空间重要的是省了代码量XD)

说点什么

您将是第一位评论人!

提醒
wpDiscuz