权值线段树是维护值域的线段树, 对于不怎么要求点之间区别的题很有帮助

权值线段树

权值线段树是普通线段树的一种特殊形式…但这里的线段树的区间记录的是节点的权值
有一些奇奇怪怪的用途比如可以求一个动态的区间中比某一个数小的数的个数
具体实现就是叶子节点(b[].le == b[].ri)的单元区间正好是节点的权值, 这也意味着节点的权值需要离散化(毕竟线段树不可能到$10^9$是不)

怎么知道一个比一个数小的节点个数捏, 先将线段树初始化为全0, 插入一个数x的时候就把区间[x, x]整体+ 1,然后查询比点y的数的个数的时候就查询[1, y]的区间和即可

然后就有一些有趣的性质啊, 比如查询的时候比y晚插入的数就算比y大也不会被计算进去的(还没在线段树里修改), 这就可以求逆序对啊, 求第k大啊什么的…

没了? 没了
本来嘛所谓权值线段树就是线段树的一种灵活的应用(新奇的脑回路)还有什么可以说的…
主要是为了给学主席树打打基础…

对于数据结构还是不能以做出题(想出思路)为目标…本来数据结构题一般思维难度不会很大…所以还是要熟练为止…最好是达到肌肉记忆1min一遍A…还是要开阔一下思维啊…

By 辣鸡 Cansult