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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.