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?
Range bit inversions and range set bit queries with a binary indexed tree
data structures;binary trees;intervals