可持久化数据结构总是可以保留每一个历史版本,并且支持操作的不可变特性
概念引入
考虑一个经典的问题:
给定
我们先考虑该问题的简化版本:
给定
我们可以用线段树维护一个频数数组[1],然后在线段树上二分[2]
我们考虑这个简化问题和原问题之间的关系:
如果我们知道
我们对原始数据按顺序更新频数数组
最暴力的想法是每次更新的时候都建立一个线段树,这样我们必然任意查询的
但是这样显然空间会爆炸,每个线段树要4倍空间,q次操作需要q个线段树,这是不可接受的
如何利用空间呢?
还记得吗,线段树每次操作最多只影响
模板与练习
待更新