I believe it can't be easily done using a segment tree. Though you can make an sqrt-decomposition of your array where for each block store cnt[] map of elements and a modifier to add to all of them. On update, add +-1 to the modifier for each block that lies entirely inside the range, and manually go through and change all remaining elements (and according cnts). On query, sum cnt[-modifier] for all inside blocks and manually count all remaining elements (not forgetting about their blocks' modifiers). Thus you'll count all zero elements, so subtract it from the range's length to get the count of non-zero