# [SOLVED] FLIPCOIN problem solution using SegmentTree has high runtime

## Issue

I’ve been trying to solve the FLIPCOIN question of CodeChef (https://www.codechef.com/problems/FLIPCOIN) but I always received the message Time Limit Exceeded.

The input is as follows: First comes a number n, the length of a row of coins, all turned tails up initially, and a number q, the number of tasks.
After that follow q tasks: updates, which have the form `0 A B` and and should flip all coins in the range (inclusive) from `A` to `B`, and queries of the form `1 A B`, where one should ouput the number of coins turned heads in the range from `A` to `B`.

I’ve already seen some solutions but I still don’t know what is the problem with my code, is it because of the class? I would like to know why my code is so slow.

``````#include <bits/stdc++.h>
#include <iostream>
#include <vector>
class SegmentTree{
SegmentTree* leftChild;
SegmentTree* rightChild;
public:
SegmentTree(int x,int y, std::vector<int> arr){
leftmost=x;
rightmost=y;
if(leftmost==rightmost){
}
else{
int mid=(leftmost+rightmost)/2;
leftChild=new SegmentTree(leftmost, mid, arr);
rightChild=new SegmentTree(mid+1, rightmost, arr);
recalc();
}
}
void recalc(){
if(leftmost==rightmost) return;
}
void rangeUpdate(int left,int right){
if(left>rightmost||right<leftmost) return;
if(leftmost==rightmost){
}
else{
}
return;
}
leftChild->rangeUpdate(left, right);
rightChild->rangeUpdate(left, right);
recalc();
}
int rangeSum(int l,int r){
if(l>rightmost||r<leftmost) return 0;
return leftChild->rangeSum(l, r)+rightChild->rangeSum(l, r);
}
};

int main(){
int n, q;
std::cin>>n>>q;
std::vector<int> vec(n);
fill(vec.begin(), vec.end(), 0);
SegmentTree st=SegmentTree(0,n-1,vec);
while(q--){
int a, l, r;
std::cin>>a>>l>>r;
if(!a) st.rangeUpdate(l,r);
if(a) std::cout<<st.rangeSum(l,r)<<std::endl;
}
return 0;
}
``````

## Solution

The reason why your code is slow is that while your range queries take logarithmic time, your range updates take linear time. When updating a range of length n, you don’t want to look at all n elements in that range. Instead, you want to make your updates lazy.

What does that mean?
If the range of a SegTree node is fully inside you queried range (`left <= leftmost && rightmost <= right`), you can just remember that you will need to update the coins in that range and recalculate the number of coins turned to heads (`n_heads = rightmost - leftmost + 1 - n_heads`) after the flip, but don’t actually do anything else (especially not doing a recursive call)
Now when do you do the update? Always before doing a recursive call to the children, you will need to `push` the stored update in the current node to them. You can do this with an `apply()` method (this will flip all the coins in a SegTree node) and a `push()` method, which will apply a lazy update, if we need one.

This will reduce your runtime for a query from O(n) to O(log n)

So you need to do the following.

1. add a `bool update = false` field to your SegTree
2. add an apply and a push method
``````void apply() {
// flip all coins in this range
// if we did not need to update our children before, now we do
// if however we did, then flipping again just undos that update, so just do no update at all
update = !update;
}

void push() {
if (!update) return;
leftChild->apply();
rightChild->apply();
// update done
update = false;
}
``````
1. update your update and query methods do call push before doing recursive calls (and reuse the apply function for applying updates)
``````void rangeUpdate(int left,int right){
if(left>rightmost||right<leftmost) return;
if(left<=leftmost&&rightmost<=right) {
apply();
return;
}
// IMPORTANT: push possible lazy update to children before updating them
push();
leftChild->rangeUpdate(left, right);
rightChild->rangeUpdate(left, right);
recalc();
}

int rangeSum(int l,int r){
if(l>rightmost||r<leftmost) return 0;