### Casio991ms's blog

By Casio991ms, history, 8 months ago,

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 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.