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;
}

CodePudding user response：

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
    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;
}

3. 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