陈立杰：时空穿梭的数据结构.pdf

①建一棵线段树，然后再每个表示区间的节点上都建一棵权值线段树！直接查询即可。 ②建n棵线段树，第i棵线段树表示1~i里面所有的数构成的权值线段树！那么查询区间的时候就直接像使用前缀和一样，每个节点表示的权值区间在这个查询的区间中拥有数的个数就是：当前节点个数减去区间左端点建的树中对应的点的数量。