Fenwick Tree Solution || Binary Search || Explained
First Learn Fenwick Tree from here :\nSimple Explanation\nhttps://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/\nAdvance Versions\nhtt
# First Learn Fenwick Tree from here :\nSimple Explanation\n[https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/]()\nAdvance Versions\n[https://cp-algorithms.com/data_structures/fenwick.html]()\n\n\n# Complexity\n- Time complexity:\nupload function: $$O(log(n))$$ \nlongest function: $$O(log(n) * log(n))$$\n\n- Space complexity: $$O(n)$$ \n\n# Code\n```\nclass LUPrefix {\npublic:\nint n;\nvector<int> BIT;\n\n    LUPrefix(int n)  {\n        this->n = n;\n        BIT.resize(n+1); //allocate space to BIT array\n    }\n    //just a standard Fenwick tree function to update a value   \n    void update(int i, int delta)\n    {\n        for(; i<this->BIT.size(); i += (i&-i)) {\n            this->BIT[i] += delta;\n        }\n    }\n    //just a standard Fenwick tree function to query till an index\n    int query(int i)\n    {\n        int sum = 0;\n        for(; i>0; i -= (i&-i)) {\n            sum += this->BIT[i];\n        }\n    return sum;\n    }\n    \n    void upload(int video) {\n        this->update(video,1); //update index = video by 1\n    }\n    \n    int longest() {\n        int low = 1, high = this->BIT.size()-1;\n        //find largest index where prefix sum till index equals index\n        //i.e. all the values from 1 to index are present\n        while(low <= high)\n        {\n            int mid = (low+high)/2;\n            if(this->query(mid) == mid) { //if condition satisfies\n                low = mid + 1; //look for a larger index\n            }\n            else {\n                high = mid - 1; //otherwise, we have to look for some smaller index\n            }\n        }\n     return high;\n    }\n};\n```
['Binary Search', 'Binary Indexed Tree', 'C++']