浅谈主席树

浅谈主席树

浅谈主席树思想以及模板

• 浅谈主席树思想以及模板
  • 主席树的原理
  • 主席树的思想
  • 主席树的应用
  • 主席树的模板
  • 主席树的题目

首先，作为一名蒟蒻，很早就听说过主席树这个高大上的名字，然而一直都不会（其实只是没敲过代码）。所以，今天就来正式的谈一谈主席树，本蒻著此文以记之

主席树的原理

它的原理十分简单，就是想办法把前后两棵线段树进行持久化并尽可能合并以节约空间。最后的空间复杂度大概是 O(nlogn)