Fenwick Tree in 5 minutes

Fenwick tree is a dynamic prefix sums array. You can:

• Add values to elements in $$$O(\log N)$$$
• Get prefix sum in $$$O(\log N)$$$

Structure

Fenwick tree is a single array. Each element $$$i$$$ has sum of elements on some range. Each range ends in its element, but they have different sizes.

Here's how the segments look for each element:

See a pattern? Sizes of ranges go like $$$1, 2, 1, 4, 1, 2, 1, 8, \dots$$$

How do we get size of range for element $$$i$$$?

So each element in fenwick array will keep the sum of its segment. Initially the array is filled with zeroes.

Adding Values

What happens when you add $$$x$$$ to element at position $$$i$$$? You need to increment $$${tre}[i]$$$ by $$$x$$$. But also, you need to update other ranges that contain this position. How do we find them?

To find such index we'll use some binary magic. Try to figure this out for yourself.

inline void add(int i, int x)
{
    for(; i < MAXN; i |= (i+1)) 
    {
        tre[i] += x;
    }
}

Getting Prefix Sum

To get prefix sum of first $$$i$$$ elements, we'll start at position $$$i-1$$$. We'll take the sum on the range for that index, and jump to the next index.

To do that, we simply subtract the range size. But, there is a cleaner solution, using bitwise magic again.

int sum(int r)
{
    r--;
    int res = 0;
    for(; r >= 0; r = (r & (r+1))-1)
    {
        res += tre[r];
    }
    return res;
}

Time Complexity

As i said at the start, time complexity for both operations is $$$O(\log N)$$$. Why?

• For addition, every iteration turns one bit into a one. So number of iterations is at most number of bits, which is $$$O(\log N)$$$.
• For sum, every iteration increases the size of the segment of ones. So number of iterations is also at most number of bits. $$$O(\log N)$$$

Full Code

const int MAXN = 200005;

struct fenwick
{
    int tre[MAXN];
 
    fenwick() {}
 
    inline void clear(int n)
    {
        for(int i = 0; i < n; i++)
        {
            tre[i] = 0;
        }
    }
 
    inline void add(int i, int x)
    {
        for(; i < MAXN; i |= (i+1))
        {
            tre[i] += x;
        }
    }
 
    inline int sum(int r)
    {
        r--;
        int res = 0;
        for(; r >= 0; r = (r & (r+1))-1)
        {
            res += tre[r];
        }
        return res;
    }
};

Conclusion

Fenwick tree is used to keep a dynamic prefix sums array with every operation being $$$O(\log N)$$$.