Proof of query and update in Binary Indexed Tree

Revision en1, by Casio991ms, 2020-05-08 20:26:41

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[a]$$$.

void update(int at, int v) 
{
    while (at < N)
    {
        bit[at] += v;
        at += at & -at;
    }
}
Tags #tutorial, binary indexed tree, bit/fenwick tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Casio991ms 2021-11-17 15:05:46 4 Tiny change: 'gnificant bit of $' -> 'gnificant set bit of $'
en3 English Casio991ms 2020-05-08 21:14:49 0 (published)
en2 English Casio991ms 2020-05-08 21:12:31 66 Tiny change: 'ranslated.' -> 'ranslated.\nYour title here...\n=================='
en1 English Casio991ms 2020-05-08 20:26:41 2710 Initial revision (saved to drafts)