## 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{
int leftmost,rightmost,n_heads;
SegmentTree* leftChild;
SegmentTree* rightChild;
public:
SegmentTree(int x,int y, std::vector<int> arr){
leftmost=x;
rightmost=y;
if(leftmost==rightmost){
n_heads=arr[leftmost];
}
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;
n_heads=leftChild->n_heads+rightChild->n_heads;
}
void rangeUpdate(int left,int right){
if(left>rightmost||right<leftmost) return;
if(leftmost==rightmost){
if(n_heads){
n_heads=0;
}
else{
n_heads=1;
}
return;
}
leftChild->rangeUpdate(left, right);
rightChild->rangeUpdate(left, right);
recalc();
}
int rangeSum(int l,int r){
if(l>rightmost||r<leftmost) return 0;
if(l<=leftmost&&r>=rightmost) return n_heads;
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.

- add a
`bool update = false`

field to your SegTree - add an apply and a push method

```
void apply() {
// flip all coins in this range
n_heads = rightmost - leftmost + 1 - n_heads;
// 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;
}
```

- 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;
if(l<=leftmost&&rightmost<=r) return n_heads;
// IMPORTANT: push possible lazy update to children before querying
push();
return leftChild->rangeSum(l, r)+rightChild->rangeSum(l, r);
}
```

Thats it!

Further improvements would be to not use individual nodes but the array representation of a binary tree (https://www.geeksforgeeks.org/binary-tree-array-implementation/) and (as has already been said) passing the vector by reference instead of by value

Answered By – Robin

Answer Checked By – Timothy Miller (BugsFixing Admin)