线段树属于一种高级数据结构。在学习线段树的时候需要的知识铺垫比较多。建议先对树状结构、二分以及递归编程法有深刻的认识和理解，然后再进行线段树的学习。
简单线段树支持单点查询，区间查询，单点修改，区间修改。
普通线段树维护的信息是数列的区间信息，比如区间和、区间最大值、区间最小值等等。在维护序列的这些信息的时候，我们更关注的是这些数本身的信息，换句话说，我们要维护区间的最值或和，最关注的是这些数总共的信息。而权值线段树维护一列数中数的个数。
来看这样一个数列：
1 1 1 2 3 3 4 5 5 6 6 7
一棵权值线段树的叶子节点维护的是“有几个1”，“有几个2”...，他们的父亲节点维护的是“有几个1和2”。
传统的线段树用于维护一条线段上的区间，可以方便地查询区间信息。而如果将线段树转化为『权值线段树』，每个叶子节点存储某个元素出现次数，一条线段的总和表示区间内所有数出现次数的总和。
利用权值线段树可以方便地求出整体第 k 大 —— 从根节点向下走，如果 k 小于等于左子树大小，说明第 k 大在左子树的区间中，在左子树中继续查找即可；否则，说明第 k 大在右子树的区间中，此时将 k 减去左子树大小，并在右子树中继续查找。
查找过程类似平衡树，时间复杂度为O(logn) 。
给定N个数（\(1~10^6\) 范围内），一共M次插入及询问，每次都要询问当前序列的第k大的数。
其中 \(M≤2×10^5\)，保证询问有答案。
该问题用平衡树可以做，但有没有更简单的做法呢？
我们考虑类比平衡树，用线段树解决。平衡树为什么可以做？因为他它证了当前节点左儿子比他小，右儿子比他大，并且维护了每个节点的size，所以可以找到k大。那我们想用线段树该怎么做呢？
这里我们转换一下思路，用每个叶子节点记录下当前自然数出现的次数。例如当前某个叶子节点管理的区间是[3,3],那么他记录的就是3这个自然数当前出现的次数。
\(\color{red}{权值线段树的节点用来表示一个区间的数出现的次数}\)
例如： 数1和2 分别出现3次和5次，则节点1 记录3，节点2 记录5， 1和2的父节点记录它们的和8 .
权值线段树维护的是桶，按值域开空间，维护的是个数。
简单线段树维护的是信息，按个数可开空间，维护的是特定信息。
参考学习：https://www.cnblogs.com/young-children/p/11787493.html
原文：https://www.cnblogs.com/tham/p/12405032.html