I have encountered following problem: There are n numbers (0 or 1) and there are 2 operations. You can swich all numbers to 0 or 1 on a specific range(note that switching 001 to 0 is 000, not 110) and you can also ask about how many elements are turned on on a specific range.

Example:

->Our array is 0100101
We set elements from 1 to 3 to 1:
->Our array is 1110101 now
We set elements from 2 to 5 to 0:
->Our array is 1000001 now
We are asking about sum from 2nd to 7th element
-> The answer is 1

Brute force soltion is too slow(O(n*q), where q is number of quetions), so I assume that there has to be a faster one. Probably using segment tree, but I can not find it...

CodePudding user response：

You could build subsampling binary tree in the fashion of mipmaps used in computer graphics.

Each node of the tree contains the sum of its children's values.

E.g.:

0100010011110100
 1 0 1 0 2 2 1 0
  1   1   4   1
    2       5
        7

This will bring down complexity for a single query to O(log₂n).

For an editing operation, you also get O(log₂n) by implementing a shortcut: Instead of applying changes recursively, you stop at a node that is fully covered by the input range; thus creating a sparse representation of the sequence. Each node representing M light bulbs either

1. has value 0 and no children, or
2. has value M and no children, or
3. has a value in the range 1..M-1 and 2 children.

The tree above would actually be stored like this:

        7
    2       5
  1   1   4   1
 1 0 1 0     1 0
01  01      01

You end up with O(q*log₂n).