这里介绍一个相对通用的办法。

使用重量平衡树（能够保证每个点子树size与自身size只比严格介于 $(c,1-c)$之间的平衡树，$c$ 为取定的常数 ）维护序列非0位置。

操作2,3和操作1的区间定位没有影响。

操作1递归访问到的总节点数也不变，唯一问题是信息合并的复杂度。而这满足递归式 $T(n)=T(c*n)+T((1-c)*n)+\log{n}=O(区间长度)$。注意及时清除区间中的0元素。

于是总复杂度仍为 $O(n\log{U}+q\log^2{n})$。

并且我们现在能支持更多操作，比如单点修改权重，对复杂度的影响只有操作1中访问的节点数，均摊代价 $O(\log{U})$；比如序列分裂合并，单次代价与区间定位相同为 $O(\log^2{n})$。

关于重量平衡树，一个OI可写的实现是一种称为 WBLT 的东西。