Proof of query and update in Binary Indexed Tree

Suppose, given array is a[N]a[N] and BIT array is bit[N]bit[N]. Now we need this bit[N]bit[N] array to efficiently store some information.

Suppose 1<=i<N1<=i<N is a given index and least significant set bit of ii is LSB(i)LSB(i). Then bit[i]=a[i]+a[i−1]+a[i−2]+...+a[i−(2LSB(i)−1)]bit[i]=a[i]+a[i−1]+a[i−2]+...+a[i−(2LSB(i)−1)].
In other words, bit[i]bit[i] stores the sum of 2LSB(i)2LSB(i) elements ending with a[i]a[i].

Query
Now, we can use this perspective to understand query function. Lets say we need to find sum from a[1]a[1] to a[at]a[at]. First we will initialize a variable ret = 0. Then we will add bit[at]bit[at] with retret and clear the last set bit LSB(at)LSB(at) from atat, because bit[at]bit[at] already contains the sum of a[at],...,a[at−2LSB(i)+1]a[at],...,a[at−2LSB(i)+1]. And clearing the last set bit means subtracting 2LSB(i)2LSB(i) from atat. We will continue the operation until we clear all the set bits in atat.

int query(int at)
{
    int ret = 0;
    while (at > 0)
    {
        ret += bit[at];
        at -= at & -at; // Side note, at &= at - 1 works the same
    }
    return ret;
}

Update
In order to update element a[at]a[at], we need to update all bit[i]bit[i] such that i>=at>i−2LSB(i)i>=at>i−2LSB(i). i=ati=at satisfies the condition. We need to prove that if i>ati>at, i0=at+2LSB(at)i0=at+2LSB(at) is the smallest index we need to update.

This contains mainly two parts. First, we must update the index i0=at+2LSB(at)i0=at+2LSB(at). The reason is that i0−2LSB(i0)<i0−2LSB(at)=ati0−2LSB(i0)<i0−2LSB(at)=at. That means bit[i]bit[i] covers a[at]a[at].

Secondly, i0i0 is the smallest index we have to update. Now suppose, i=at+ki=at+k, where 1<=k<2LSB(at)1<=k<2LSB(at).

:: 2LSB(k)<=2MSB(k)<=k<2LSB(at)2LSB(k)<=2MSB(k)<=k<2LSB(at)
:: MSB(k)<LSB(at)MSB(k)<LSB(at)
:: There is no common set bit in at and k, because maximum set bit of k is less than the minimum set bit of at
:: LSB(i)=LSB(at+k)=min(LSB(at),LSB(k))=LSB(k)LSB(i)=LSB(at+k)=min(LSB(at),LSB(k))=LSB(k)

Then, i−2LSB(i)=i−2LSB(k)>=i−k>=ati−2LSB(i)=i−2LSB(k)>=i−k>=at. So, bit[i]bit[i] doesn't cover a[at]a[at].

So, the proof is that i0=at+2LSB(at)i0=at+2LSB(at) is the smallest index needs to be updated. Now notice, our condition for Update was i>=at>i−2LSB(i)i>=at>i−2LSB(i). As we have found i0i0 is the smallest index we need to update, so any subsequent ii must satisfy i>=i0>at>i−2LSB(i)i>=i0>at>i−2LSB(i). So, if we replace atat with i0i0, we will get the same subsequent set of ii. That's why to update a[at]a[at], then atat will be updated as at += 2 ^ LSB(at) after updating bit[at]bit[at].

void update(int at, int v) 
{
    while (at < N)
    {
        bit[at] += v;
        at += at & -at;
    }
}

Credit goes to DrSwad. I just translated.