''Euler tour technique' and 'Lazy Segment Tree' based on CF 877E

It took me almost a century to get this problem and this algorithm right, but I really learn a lot about how this algorithm works.

Getting right after the algorithm works

Problem Link:  Problem - 877E - Codeforces
In this problem, the lights are in a tree. There are two kinds of operations that we need to do. For the first, we are asked to do operations for each we switch the lights on one vertex and its children. For the second, we need to keep track of the number of lights among one vertex and its children that is on.

 It is similar to a classic segment tree problem called the flip-coin problem which directly use the segment tree. However flip-coin problem is about doing operations on a row of coins, while we have a tree here.

However, we can use Euler Tour Technique to convert it into a flat row. In the example above, we can convert the tree into the sequence:

1 2 2 3 3 4 4 1

where we can get the answer of, for example, "get 1" by calculating the sum between the two '1's and divide it by two. Then the problem turns into reversing the numbers in an interval and getting the sum of an interval.

Then it comes to segment tree.
The original version of segment tree can get the sum of an interval in O(log(n))time, but it can only update a single element. It will be very time-consuming if we directly apply it since the complexity of a single query will become O(n * log(n)) However, if we, instead, used a lazy propagation version of segment tree, the time of updating range could be O(log(n)).

There is a video on YouTube about lazy propagation: Segment Tree - Range Queries with Lazy Updates
(If you are not familiar with segment tree, hope this will help: Segment Tree - GeeksforGeeks)

We maintain a bool array called lazy here. When lazy[x] is true, it means, its two children(if any) should be flipped. 
For the query part here,

int query(int a, int b, int x, int l, int r) {
int mid = (l + r) / 2;
    if(r < a || l > b) return 0;
    if(lazy[x] && l < r) {
        lazy[x] = false;
        lazy[(x<<1) + 1] ^= 1;
        lazy[(x<<1) + 2] ^= 1;
        dat[(x<<1) + 1] = (mid - l + 1) - dat[(x<<1) + 1];
        dat[(x<<1) + 2] = (r - mid) - dat[(x<<1) + 2];
    }
    if(l >= a && r <= b){
    return dat[x];
}
    
    int lquery = query(a, b,  (x<<1) + 1, l, mid);
    int rquery = query(a, b, (x<<1) + 2, mid+1, r);
    return lquery + rquery;
}

For the update part here:

void update(int a, int b, int x, int l, int r) {
int mid = (l + r) / 2;
    if(r < a || l > b) return ;
    if(lazy[x] && l < r) {
        lazy[x] = false;
        lazy[(x<<1) + 1] ^= 1;
        lazy[(x<<1) + 2] ^= 1;
        dat[(x<<1) + 1] = (mid - l + 1) - dat[(x<<1) + 1];
        dat[(x<<1) + 2] = (r - mid) - dat[(x<<1) + 2];
    }
    if(l >= a && r <= b) {
        if(l != r) lazy[x] ^= 1;
        dat[x] = (r - l + 1) - dat[x];
        return ;
    }
    
    update(a, b, (x<<1) + 1, l, mid);
    update(a, b, (x<<1) + 2, mid+1, r);
    
    dat[x] = dat[(x<<1) + 1] + dat[(x<<1) + 2];
}

Look what is noteworthy here. There is a common part that are both in query and update function: the propagation part. Actually we can factor that out. (See my final code below)

As we learn, the essence of lazy propagation is that we will keep the 'flipped' status in the lazy tree and not flip it until we need to use it. As a result, we can update it with only a time complexity of (O(log(n)), which is a lot faster than the original version while doing such interval sum update.

Here is my code on this problem:  Submission #32038974 - Codeforces.

Here's my first blog and thanks you guys again for your attention!

Thanks the sources below for helping me learn a lot!
- FLIPCOIN - Codechef
- Codeforces Round #442 (Div.2). Editorial. - Codeforces