I was recently solving this problem : http://poj.org/problem?id=1823
The problem basically says given an array of maximum size of 16000 where each element is one or zero, we need to perform the following two operations.
-Set range [L,R] to ones or zeros.
-Query maximum length of a subarray of ones
The problem can be indeed be solved by a segment tree, however using bitset we can do updates in O(N/32), and with N being 16000 that's just 500.
The problem is in querying the maximum length, I haven't reached any solution better than N operations, are there any ways to achieve something like N/32 ?
Please note, I already know the segment tree solution, I'm interested in bitset.