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

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