A code for a CodeChef Problem . Level: Medium. Name: FlipCoins

flip_coin.c

// This question was solved using Segment Tree Data Structures.
// Refered to : https://www.codechef.com/viewsolution/20334199
//            : https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/

#include <iostream>

using namespace std;

#define NMAX 100001

int N, Q, A[NMAX * 4];
bool add[NMAX * 4];

void Update(int, int, int, int, int);
void Fix(int, int, int);
int Query(int, int, int, int, int);

int main()
{
    cin >> N >> Q;

    for (int i = 1, cer, a, b; i <= Q; i ++)
    {
        cin >> cer >> a >> b;

        if (cer == 0)Update(1, 0, N - 1, a, b);
        else cout << Query(1, 0, N - 1, a, b) << '\n';
    }
    return 0;
}
void Update(int node, int a, int b, int l, int r)
{
    Fix(node, a, b);

    if (a > r || b < l)return;

    if (l <= a && b <= r)
    {
        add[node] = !add[node];
        Fix(node, a, b);
    }
    else
    {
        int mijl = (a + b) / 2;

        Update(2 * node, a, mijl, l, r);
        Update(2 * node + 1, mijl + 1, b, l, r);

        A[node] = A[2 * node] + A[2 * node + 1];
    }
}
int Query(int node, int a, int b, int l, int r)
{
    if (a > r || b < l)return 0;

    Fix(node, a, b);

    if (l <= a && b <= r)return A[node];
    else
    {
        int mijl = (a + b) / 2;
        return Query(2 * node, a, mijl, l, r) + Query(2 * node + 1, mijl + 1, b, l, r);
    }
}
void Fix(int node, int a, int b)
{
    if (add[node])
    {
        int n = b - a + 1;
        A[node] = n - A[node];

        if (a != b)
        {
            add[2 * node] = !add[2 * node];
            add[2 * node + 1] = !add[2 * node + 1];
        }
    }
    add[node] = 0;
}