相比较普通的线段树,权值线段树存的是每个区间的出现的次数,查找的时候也是根据这个权值来查找。
题意
开始是一个空的序列,每次一个询问L,R,代表把L到R这R-L+1个数字加入到序列当中,每次放完,输出当前序列的中位数
思路
在这个题中,叶子节点存的也是一段区间,这段区间的个数不和普通的线段树一样,它的个数是人为确定的。我们把所有L,R离散化到一个数组中,还有注意的是R要先+1在存到数组中,这样存的就是一个左闭右开的区间了。然后初始建树的时候每个叶子节点存的区间就包括了所有的L,R区间。然后更新的时候,我们更新的是这个区间出现的次数,比如说第一次[1,3],第二次[1,4], 那么存[1,3]这段区间的那个线段树节点的权值就是2,因为它出现两次。
1 |
|