I read this on Quora. Hope you find it useful. There are things that a segment tree can do but a BIT cannot : A BIT essentially works with cumulative quantities. When the cumulative quantity for interval [i..j] is required, it is found as the difference between cumulative quantities for [1…j] and [1…i-1]. This works … Read more
[EDIT: I had things “upside-down” — fixed now!] Yes. Loop through the n array items in increasing index order, always adding the sum only to the next smallest index that it should be added to, instead of to all of them: for i = 1 to n: j = i + (i & -i) # … Read more
Let me assume that negative value is represented using two’s complement. In this case, -i can be calculated as (~i)+1 (flip bits, then add 1). For example, let me consider i = 44. Then, in binary, i = 0000 0000 0000 0000 0000 0000 0010 1100 ~i = 1111 1111 1111 1111 1111 1111 1101 … Read more