3
$\begingroup$

I am trying to solve this problem using a binary indexed tree. The problem can be summarized as follows:

You are given a series of commands that operate on an array initially all zeroes.

1) Invert all bits from [a, b] (1 becomes a 0 and vice-versa)

2) Find the number of set bits from [a, b] (bits that have value 1).

I know that one way to solve this is using a segment tree with lazy propagation, but I want to see whether it can be solved using a binary indexed tree.

To start, I know that binary indexed trees can be used to do range increments and range sums as per my previous question.

Further, I know that the structure of a binary indexed tree is that the node $i$ stores a function of values form $i - 2^h + 1$ to $i$ where $h$ is $i \text{ and}-i$ which is sort of similar to a segment tree in which each node stores the merged value of its left and right children (2i and 2i + 1 in the array representation).

Binary indexed trees only operate on functions that are associative and have an inverse, (that is, function[a..b] = function[0..b] - function[0..a-1]). On the other hand, segment trees only need a function that is associative, as the range is built directly from smaller segments rather than being a difference of two other ranges.

Finding the number of set bits does seem to be a function where numSetBits[a...b] = numSetBits[0...b] - numSetBits[0...a-1]

except that inversion is not such a function. Could binary indexed trees somehow be cleverly modified (like was done to support range queries and updates) in order to solve this problem?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Can you explain what is an associative function? I know the concept of associative operators, but not certain on associative function. $\endgroup$ – InformedA Dec 3 '14 at 5:09
  • $\begingroup$ I don't think associative function is a formal term. Just one I made up. It is essentially a function that can operate across a range of values (like addition where you add each element in the list) and the following is true: f[a..b] + f[b..c] = f[a..c]. $\endgroup$ – 1110101001 Dec 3 '14 at 5:19
  • $\begingroup$ In that case, you need to have a kind of ordering on the function's domain which is also not a thing I know of when defining a function. $\endgroup$ – InformedA Dec 3 '14 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.