Are Segment Trees needed to query range set problem?

Intuitively it seems that this requires usage of Segment trees. Can anybody comment on whether I am think on the correct line?

I think Segment Trees will TLE for this problem. I think the intended solution is something like this.

Make an array of size 10^7. Suppose you get a query to update [a,b] then in the array(let’s call it X) add 1 to X[a] and 1 to X[b + 1]. Then to get the bit on ith point we just get sum from X[1] to X[i], let’s call it S. Then the bit on ith point is S % 2. To get all the bits of array we just do 1 linear swap. Now Divide the array into blocks of 4 and find the frequencies.

2 Likes

suppose you got the sum for ith point then rather then computing sum again for (i+1)th point you just add X[i + 1] to sum for ith point and get the sum for (i+1)th point. In this way you get all the bits in 1 linear swap

[This][1] will be helpful.
[1]: http://codeforces.com/blog/entry/14266

2 Likes