Hi everyone,

Today i've released a video about a crazy problem:

link

Its a problem like you've never seen before. I've encountered it back in 2018 and i was able to solve it only recently.

Link to the problem: link

Let me know the craziest problems that you ever saw!

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

Dynamic Programming Video pt. 2

Hello everyone!

Me and DJeniUp are back with another programming video!

https://www.youtube.com/watch?v=dv_dGwrazuE

This video is about a tricky problem that i've encountered at my first ever programming competition. At first glance it seems like a simple strategy will cut it, but as you submit more and more solution, you start to realize it's not that simple...

This video is about interval dp, and you can solve the problem for yourself: https://codeforces.me/gym/106465/problem/A

PS: Thanks everybody for 1k subscribers!

Hello Everyone!

Me and DJeniUp recently started a YouTube channel dedicated to competitive programming.

Today, we released a new video! It's about Dynamic Programming:

Link: https://www.youtube.com/watch?v=eNjDWXugJCo

Feel free to leave your feedback and suggestions under the comments, we appreciate those!

Hello Everyone!

Recently, me and DJeniUp started a YouTube channel, dedicated to algorithms, math and competetive programming in general.

Today we released a new video on a topic of Topological Sort!

Link: https://www.youtube.com/watch?v=EJoKJiod0KQ

Feel free to leave your suggestions in the comments under the video or this blog! We would like to explore more competetive programming topics, from basic to complicated ones

Here's the link to the whiteboard that you see in the video: https://miro.com/app/board/uXjVGcpqFXU=/

All codes can be found there or on our github: https://github.com/Lincatoria/VideoMaterials

Centroid Decomposition is kinda like Divide & Conquer on arrays (merge sort type divide&connquer) but for trees. Ever thought about it that way? Like HLD is a segment tree but for trees, what do you think? nvm just had a fun thought yesterday, never looked at it from this angle, cool (i attached some imagery)