前言

在写注意事项之前，我先带着你熟悉一下主席树的基本实现思想。

主席树的基本用途

给你一个长度为n的数列
处理多次查询给定的[l,r]区间内第k大(小)数的问题

主席树的实现原理

其本质就是建立n+1颗线段树(n是区间内数字个数)，但是在建立线段树的时候重复利用了之前已经建好的节点，从而节省了空间。

如何建立、并管理好n+1颗线段树

建立分下面两步：

1. 建立一颗空的线段树
2. 依次将数列的n个数