「OI」可持久化线段树

可持久化线段树的代表有主席树(可持久化权值线段树)等。

简介

可持久化线段树其实并不难。

它是一种经过优化的朴素数据结构。

我们为了解决问题,有可能会在每个点上都用线段树储存一些信息,可是每一个节点上都开一颗线段树的话实在是浪费空间( $ \Theta ( n ^ {2} ) $ ),但是我们可以发先有一些数据并没有发生过变化,我们只需要修改一条链即可,时空复杂度均为 $ \Theta ( \log _ {2} n ) $,继而总的空间复杂度为 $ \Theta ( m \log _ {2} n ) $,其中 $ m $ 为版本数量。