ivplay's blog

By ivplay, history, 3 weeks ago, In English,

What is the proof that from any index idx , idx + (idx&-idx) is the next closest index that covers idx? I mean how can I prove that no other index in range ( idx,idx+(idx&-idx) ) actually covers idx? '(' means exclusive and covers idx means contains information of idx ??

Thanks in advance.

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Its because the (x & -x) gets you the least significant bit of x.

let a=[A]10...00, then (thanks to 2-complements) -a = [A inverted]01...11 + 1 or [A inverted]10...00. Bitwise ANDing the two gets 000010...000, or the lsb of a.

For the covering, its because the length of the interval corresponding to x is equal to 2^(lsb) 1-indexed

You can check out my blog if this isn't clear.

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

First lets proof idx + (idx&-idx) covers idx

idx&-idx = 2^x = P (let), where x is the lowest significant bit of idx.

according to binary addtion 1 + 1 = 0 and we carry a 1 to right.

so if z is the lsb of idx + P then z > x

so, idx+P-2^z < idx+P-2^x

=> idx+P-2^z < idx

so idx+P covers idx.

now lets proof P is lowest such amount that we need to add with idx to get the number that covers idx.

If P is not the lowest such amount then let Q < P and idx + Q covers idx.

since Q < P and P = 2^x

it's obvious that y < x where y is the lowest significant bit of Q

since x is the lsb of idx and y is lsb of Q and y < x then of course y is the lsb of idx+Q (binary addtion, 1 + 0 = 1 )

As y is the lsb of Q so, Q >= 2^y

Hence, idx + Q-2^y >= idx

So idx+Q does not cover idx according to BIT property.

Proof by contradiction, P = idx&-idx = 2^lsb_of_idx is the lowest amount we have to add to get the number that covers idx.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    btw if i can add to this , the BIT property/objective is if the least significant bit of i in binary is x, tree[i] will contain cumulative result of (i-2^x+1)th to ith element

    for example for i=20 , binary(20) = 10100 . so tree[20] will contain cumulative result of decimal(10000)+1 to decimal(10100) => 17th to 20th element