我先前不知道什么叫权值线段树，是通过一道题目我才知道的。
那道题目就是逆序对。（非常经典的一道题
所以我们先不谈什么是权值线段树。
先思考这道题如何用线段树解决。
首先，你现在拥有一段序列，这个序列很长 （n<=1e7) ,然后这个序列里的每个数，取值范围在[-1e9,1e9]
请你求出这段序列里面逆序对的个数。（这里定义的逆序对就是 ，i<j ，ai > aj ，也就是从1~n不单调递减的元素对数）
沃兹及 说 ：大部分的算法都是起源于暴力?。
我们先不管会不会超时，我们从暴力算法中找找灵感。
对于任意一个元素 i ，我们只要找[ 0, i-1 ]中有多少个数比i大就好了。
所以只需要从第一个元素开始，不断找它左边比他大的元素的个数就行。
怎么找？
我们假设有一条实数轴，实数轴的下标是[-1e9 , 1e9 ] ，但是实数轴现在是空的。
把下标理解为一个桶的话，就是每个桶内都是空的。
假设我们现在有6个数：? -11 ，-18 ， -118 ， 11 ，118 ， -71 .?
我们现在按照顺序：
1、先查找-11有多少个逆序对（也就是找-11右边的桶内有几个元素）
结果是0个（因为它是最开始的元素），
2、现在我们把-11 放入对应的桶内。
然后看-18 ，找-18右边的桶内有几个元素.....找到了，有-11这一个元素。
答案 ans =1 (目前有一个逆序对）
3、我们把-18?放入对应的桶内.
然后看-118 ，找-118右边的桶内有几个元素.....找到了，有-18、-11这俩个元素
答案 ans =3?(目前有三个逆序对）
再把-118放入对应的桶。
4、然后找11，发现11右边无元素，放11. 答案 ans = 3+0 =3
5、找118，发现118右边无元素，放118. 答案 ans = 3+0 =3
6、找-71，发现-71右边有：-18、-11、11、118 四个元素，
答案 ans= 3+4 =7 ；
最后把-71放入桶子内。
好的，这个过程模拟完了，我相信你有疑问了。
那就是，我们如何查找它右边有几个桶？或者，为啥保证这样做就是对的呢？
一个一个回答：
一、为什么这样做是对的？
事实上，我们只要保证从题目给的序列的第一个数开始（查询+更新）就可以了。
因为在这条数轴中，假如我们现在要（查询+更新）i这个数，那么当前数轴的桶内有的数一定是在i的前面就（查询+更新过了）
如果有数在i 这个桶的右边，那么它们和i一定是逆序对，个数就是i右边元素的个数。
二、
我们如何查找它右边有几个数？
别忘了，线段树不就是维护线段的吗。
当我们不给他初始化值的时候，他不就是一个充满桶子的数轴吗？
只不过我们现在令桶子为空即可。
(如果长度太大，一定要离散化）
我们只要开个结构体，用 tree[i] .box 表示桶子就可以了。
然后怎么数一个数a，右边的所有的桶子内的元素有多少个？
假设没有离散化，那么你只要求 [ a+1, n ] 的区间和就行了 （这里的区间和指的是tree[i].box）
别跟我说不会求区间和。。。。
假如这个数a比较大，线段树开不了那么多空间，怎么办？
那么你离散化一下，求这个数a离散化后的坐标pos。
拿上面 的数举例子吧：? -11 ，-18 ， -118 ， 11 ，118 ， -71 .?
离散化后的下标就是：
num: -118, -71,? -18, -11 , 11 , 118
pos:? ?1 ,? ? ? 2 ,? ? 3 ,? ? 4,? ? 5,? ? ?6
比如现在你要求 -18右边的桶子有多少元素，那么你只要求[ 3+1 , n]的区间和就行了。
（切记，求完区间和之后一定要更新box 的值，就是查找到 离散化后的下标的位置，然后把那个位置上的 box ++ ）
嗯。。。。上代码：
那么，这就是权值线段树。
我总结一下（仅代表个人观点）
权值线段树其实就是，建一颗空的树，然后开个结构体保存一下每个点的权值。
它和普通线段树最不一样的地方就是：
（还是拿刚刚的序列举例）
? -11 ，-18 ， -118 ， 11 ，118 ， -71 .?
普通线段树，会把-11 放在 tree【0】
而权值线段树，会把 -11放在其相对大小应该在的地方也就是? tree【4】
所以，这使得这棵树是递增的。
我们可以用权值线段树进行很多应用。
比如说求整个区间内，第 k小的数、第k大的数.
比如求逆序对。
等等等等。。。
现在还没更新完，因为我做题少，等我做多点题，再更新，大家见谅，我的内容可能会出错。