主席树(静态) 学习笔记

在学习主席树之前

你必须学习:
  1. 线段树。
  2. 前缀和。
  3. sort函数、unique函数以及lower_bound函数的使用方法。

什么是主席树

主席树又叫函数式线段树,又名可持久化线段树。所以主席树的名称与他的功能一点关系都没有。 主席树的时空复杂度为$O(n logn)$。

主席树的模板

由于主席树比较难理解,所以结合代码理解一下: 首先来看一看模板题: P3834 【模板】可持久化线段树 1(主席树) 这里放一下代码: 例题: SnackDown 2017 Online Elimination Round Prefix XOR 详情见这篇博客

评论

  1. GREED_VI

    所以说您还没有理解主席树,只会板子对吗

    7月前
    2019-2-23 20:53:46

发送评论


				
上一篇
下一篇