[C++] Scan with Prefix Sum, O(n), Explained with Simple Visualization
Intuition\n### We can classify each element x into three categories:\n P: Good/Pivot i.e. left <= x <= right: it can form a Pivot\n L: Low/Aux i.e. x < left : i
# Intuition\n### We can classify each element x into three categories:\n* P: Good/Pivot i.e. left <= x <= right: it can form a Pivot\n* L: Low/Aux i.e. x < left : it can contribute to a nearby pivot if reachable.\n* H: High/Barrier i.e. right < x: it is a barrier that split the array into subarrays,\n  and each subarray becomes an independent subproblem, which is great for problem solving.\n  It\'s a place to reset the internal accumulators in our code.\n\n### Visualization:\nIf we use P to represent a Pivot, and `-` for a low/aux element, and `|` for a High element, then the input array can be visualized as:\n        \n\n    Left:  6\n    Right: 8\n    Array:         128123612 9 612368 9\n    Visualization: --P---P-- | P---PP | \nWith proper visualization, it\'s easier to come up with algorithms.\n\n# Approach\nLet\'s scan the array from left to right.\n* If the current element is a Pivot, then itself is a good subarray,\nand it can form (psum+aux) subarrays with the Pivots and Aux elements before it.  \n* If the current element is an Aux, then it can form (psum) subarrays with the privots and the aux elements before its nearest pivot. \n* If the current element is a Barrier/High, then it splits the input array into subproblems, and the array elements to its rightside forms an independent subproblem. Thus we clear the accumulators. \n\n`psum` is the count of elements since the first reachable pivot or aux, until the last pivot before current element.\n`aux` is the count of aux elements since the last pivot before current element.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution {\npublic:\n    // Idea: O(n) fast algorithm: Scan with prefix sum\n    int numSubarrayBoundedMax(vector<int>& v, int left, int right) {\n        // Idea: scan for pivots, and accumulate the result.\n        // we can classify each element x into three categories:\n        // P: Good/Pivot i.e. left <= x <= right: it can form a Pivot\n        // L: Low/Aux i.e. x < left : it can contribute to a nearby pivot if reachable.\n        // H: High i.e. right < x: it is a barrier that split the array into subarrays,\n        //    and each subarray is an independent subproblem.\n        //    It\'s a place to reset the internal accumulators in the code.\n        // Scan:\n        // --P---P--|P---PP|  ==>\n        // distilled representation: <PivotPos, CountOfPrecedingAuxElements>:\n        // <2, 2>, <5,2>, <6,2>\n        // but we actually don\'t need to store the Pivot Pos\n        int res = 0;\n        int aux = 0; // count of the auxilliary elements in the current span.\n        int psum = 0;\n        for (int a : v) {\n            if (a > right) {\n                // High: it is a barrier that split the array into subarrays,\n                //    and each subarray is an independent subproblem.\n                aux = 0;\n                psum = 0;\n            } else if (a < left) {\n                // Low/Aux: it can contribute to a nearby pivot if reachable.\n                ++aux;\n                res += psum;\n            } else {\n                // Good/Pivot i.e. left <= x <= right: it can form a Pivot\n                psum += aux + 1;\n                res += psum;\n                aux = 0;\n            }\n        }\n        return res;\n    }\n\n    int numSubarrayBoundedMax_O_NSqaured(vector<int>& v, int left, int right) {\n        // Idea: scan for pivots, and accumulate the result.\n        // we can classify each element x into three categories:\n        // P: Good/Pivot i.e. left <= x <= right: it can form a Pivot\n        // L: Low/Aux i.e. x < left : it can contribute to a nearby pivot if reachable.\n        // H: High i.e. right < x: it is a barrier that split the array into subarrays,\n        //    and each subarray is an independent subproblem.\n        // Scan:\n        // --P---P--|P---PP|  ==>\n        // distilled representation: <PivotPos, CountOfPrecedingAuxElements>:\n        // <2, 2>, <5,2>, <6,2>\n        // but we actually don\'t need to store the Pivot Pos\n        int res = 0;\n        vector<int> spans;\n        int aux = 0; // count of the auxilliary elements in the current span.\n        for (int a : v) {\n            if (a > right) {\n                // High: it is a barrier that split the array into subarrays,\n                //    and each subarray is an independent subproblem.\n                spans.clear(); // reset, for the next subproblem.\n                aux = 0;\n            } else if (a < left) {\n                // Low/Aux: it can contribute to a nearby pivot if reachable.\n                ++aux;\n                // todo: optimization: we can have a prefix sum here\n                for (const int span : spans) {\n                    res += span + 1;\n                }\n            } else {\n                // Good/Pivot i.e. left <= x <= right: it can form a Pivot\n                res += aux + 1;\n                for (const int span : spans) {\n                    res += span + 1;\n                }\n                spans.emplace_back(aux);\n                aux = 0;\n            }\n        }\n        return res;\n    }\n};\n```
['C++']