我们先从一道经典题来入手吧
你需要维护一个数据结构，支持插入一个数，以及询问当前第k大的数是什么
我们用平衡树自然是可以做的，但有没有别的更简单的做法呢？
我们考虑类比平衡树，用线段树解决。平衡树为什么可以做？因为他它证了当前节点左儿子比他小，右儿子比他大，并且维护了每个节点的size，所以可以找到k大。那我们想用线段树该怎么做呢？
这里我们转换一下思路，用每个叶子节点记录下当前自然数出现的次数。例如当前某个叶子节点管理的区间是[3,3],那么他记录的就是3这个自然数当前出现的次数。那么对于任意一个节点管理的区间是lr，那么他记录的就是自然数lr一共出现了多少次。
我们每次插入就是相当于线段树上单点修改。查询k大的操作类比一下平衡树就行了。
这种线段树被称作权值线段树。权值线段树有什么好的呢？但我们再观察观察，就可以发现一个非常惊人的事情，两颗权值线段树可以类似前缀和直接做减法！！比如我们用插入了b以后的权值线段树减去插入a之前的权值线段树得到的权值线段树，得到的权值线段树就相当于只插入a到b之间的数的权值线段树！！我们可以用这个性质干什么呢？某些读者可能已经想到了。区间K大！！！
这种类似前缀和用权值线段树的东西就叫做可持久化线段树，也叫主席树。关于主席树的详解强烈推荐孤独·粲泽dalao的博客
带修的主席树也不难，如果我们朴素的用类似前缀和的修改的话复杂度是$O(n log n)$的。
那么有没有更快一点的修改速度呢？有。树状数组。
其实树状数组本质就是用一个正整数关于二的不重复次幂的唯一分解性质优化前缀和，使查询与修改都变成了$O(log n)$
主席树就像一颗颗权值线段树的前缀和，我们也可以用树状数组优化他，使得查询与修改复杂度都变为$O((log n)^2)。