Recently I came up with a range problem when thinking about a hobby project.

Consider a big binary array indexed from 0 with size A(“[0, A)”), I want to support 3 range (the ranges are defined to be “[left, right)” but isn’t very important and can be changed on demand) operations:

1. RangeSet(v, left, right) that sets a range to a value. For example 00000 after RangeSet(1, 1, 3) would be 01100.
2. RangeIntersectQuery(left, right) which finds the intersection between a range and all the 1s(or 0s) in the array, then merging the result into a list of ranges. For example, RangeIntersectQuery(1, 5) on 011010010 would be a list of ranges ([1, 3), [4, 5)). I’m not sure whether the order of the ranges would matter in the future, but likely that the list can be degraded to an unordered collection.
3. RangeQuery(left, right) which checks if an interval is full of 1s(or 0s). For example, RangeQuery(3, 5) on 00010110 would be false while RangeQuery(5, 7) would be true.

Ideally, all operations only concerns 1s, but supporting 0s shouldn’t create much trouble.

I was thinking that segment tree should be able to solve operation 1 and 3 in O(logA) time and O(k*A) total memory. However, I’ve trouble coming up with a good way to handle operation 2.

A can be quite big and I don’t really want O(A) time on the 3 operations, I want them to be sublinear.

I’m looking for an algorithm/data structure that can solve my problem.