C++ prefix sum with detailed explaintaion
O(N) time, O(N) space\n\nint firstDayBeenInAllRooms(vector<int>& nextVisit) {\n        //key realization:\n        //1. only move forward when current room is v
O(N) time, O(N) space\n```\nint firstDayBeenInAllRooms(vector<int>& nextVisit) {\n        //key realization:\n        //1. only move forward when current room is visited even times(to be specific, twice). \n        //2. whenever we reach a new room, all previous rooms must have been visited even times.\n        int n = nextVisit.size();\n        //pre is prefix sum, pre[i] means the first day we visit ith room\n        //for example, pre[3] = 5 means we visit room 3 on day 5, pre[7] = 10 means we visit room 7 on day 10, then to go from room 3 to room 7, it takes pre[7]-pre[3]+1 = 6 days. notice that we add 1 because we need to include day 5, which is pre[3]. \n        vector<long> pre(n);\n        long day = 0;\n        int room = 0;\n        int mod = 1e9+7;\n        while(room<n-1){\n            //in each iteration of while loop, we visit a brand new room, so the assumption here is that we visit the current new room once, and all previous rooms have been visited even times.\n            pre[room] = day;\n            //when next room to visit is itself, we can proceed to next unvisited room, but we need to revisit current room again first \n            if(nextVisit[room]==room) day++;\n            //when next room to visit is previous visited rooms, we don\'t go through the repeated steps and recalculate, we can simply use prefix sum to quickly calculate how many days we need to get back to current room again. the formula is explained above.\n            //a trick here is (value_to_calculate+mod)%mod.\n            else{\n                day = (day+pre[room]-pre[nextVisit[room]]+1+mod)%mod;\n            }\n            day++;\n            room++;\n        }\n        return (int)day%mod;\n    }\n```
[]