离散化
此坑待填
权值线段树
权值线段树的每个节点用来维护在[l,r]区间内数的个数,通常用来求k大值,时间复杂度为log n。
比如对于长度为10的数组[1,1,2,3,3,4,4,4,4,5],我们可以构造权值线段树如下。
具体操作同普通的线段树qwq……
下面是主席树
主席树是一种可持久化线段树,对于每次操作,可以保留历史版本,便于查询,是一棵权值线段树每次复制一条链得到。
比如对于最经典的求区间k大值问题:
对于长度为10的数组a,如果我们只用权值线段树的话,那么为了求[l,r]区间的k大值,我们需要建立10棵权值线段树,分别用Ti记录插入a[i]后的权值线段树。
但是这样会浪费掉很大空间,因为每插入一个a[i],只会有一条链的值发生变化,所以我们可以只建立一棵权值线段树,然后每插入一个a[i],就复制需要改变的那一条链,将它与剩余节点相连,假装是一棵新建的树……
如图,黄色的圈就是插入一个值的时候,将对应的链复制过来并修改,假装是一棵新的树Ti。
以此类推,如果数组有n个节点的话,这样下来就会保留n个版本,也就是n棵假装的树。
每次查询[l,r]区间的k大值,就可以递归找使Tl和Tr两棵树的节点个数差为k的区间。
头疼的一批,顶不住了,不如上板子。
(板子并不是k大值
(注意update函数中的&
1 |
|
近期评论