Hello!

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 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 I later noticed that since N is just 16000, we would only have blocks of size 500 ( 16000/32 = 500 ). Now the set, and reset updates part can be done in O(block).

What is remaining is how to query the number of ones, are there any possible bit operations to perhaps do? I only have O(N) solutions..

Please note, I already know the segment tree solution, I'm interested in bitset.