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

Suppose $$$1 <= i < N$$$ is a given index and least significant set bit of $$$i$$$ is $$$LSB(i)$$$. Then $$$bit[i] = a[i] + a[i - 1] + a[i - 2] + ... + a[i - (2 ^{LSB(i)} - 1)]$$$.

In other words, $$$bit[i]$$$ stores the sum of $$$2 ^ {LSB(i)}$$$ elements ending with $$$a[i]$$$.

**Query**

Now, we can use this perspective to understand query function. Lets say we need to find sum from $$$a[1]$$$ to $$$a[at]$$$. First we will initialize a variable `ret = 0`

. Then we will add $$$bit[at]$$$ with $$$ret$$$ and clear the last set bit $$$LSB(at)$$$ from $$$at$$$, because $$$bit[at]$$$ already contains the sum of $$$a[at], ..., a[at - 2 ^ {LSB(i)} + 1]$$$. And clearing the last set bit means subtracting $$$2^{LSB(i)}$$$ from $$$at$$$. We will continue the operation until we clear all the set bits in $$$at$$$.

```
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]$$$, we need to update all $$$bit[i]$$$ such that $$$i >= at > i - 2 ^ {LSB(i)}$$$. $$$i = at$$$ satisfies the condition. We need to prove that if $$$i > at$$$, $$$i_0 = at + 2 ^ {LSB(at)}$$$ is the smallest index we need to update.

This contains mainly two parts. First, we must update the index $$$i_0 = at + 2 ^ {LSB(at)}$$$. The reason is that $$$i_0 - 2 ^ {LSB(i_0)} < i_0 - 2 ^ {LSB(at)} = at$$$. That means $$$bit[i]$$$ covers $$$a[at]$$$.

Secondly, $$$i_0$$$ is the smallest index we have to update. Now suppose, $$$i = at + k$$$, where $$$1 <= k < 2 ^ {LSB(at)}$$$.

:: $$$2 ^ {LSB(k)} <= 2 ^ {MSB(k)} <= k < 2 ^ {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)$$$

Then, $$$i - 2 ^ {LSB(i)} = i - 2 ^ {LSB(k)} >= i - k >= at$$$. So, $$$bit[i]$$$ doesn't cover $$$a[at]$$$.

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

after updating $$$bit[at]$$$.

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

Credit goes to DrSwad. I just translated.