Casio991ms's blog

By Casio991ms, history, 4 years ago, In English

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.

Full text and comments »

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