3 Solutions: Fenwick Tree or Binary Indexed Tree | Segment Tree | Disjoint Set ADT
This discussion thread includes 3 separate solutions using different data structures namely,\n\n1. Fenwick Tree or Binary Indexed Tree\n2. Segment Tree\n3. Disj
This discussion thread includes 3 separate solutions using different data structures namely,\n\n**1. Fenwick Tree or Binary Indexed Tree\n2. Segment Tree\n3. Disjoint Set**\n\nThe intuition behind fenwick tree and segment tree solution is,\n=> We want to find the Longest Uploaded Prefix,\n=> Let\'s create an array of size n\n=> Let\'s consider 0 at the particular index when the video hasn\'t yet uploaded and 1 as uploaded.\n=> Now the questions boils down to, we are interested in finding the longest consecutive ones starting from 0th index\n=> What if we calculate the prefix sum, to find whether there exist all ones or is there any 0 in that portion, FOR EXAMPLE: In this array  [1, 1, 1, 1, 0, 1] if we calculate the prefix sum till 3rd index it would be 4 and also there are only 4 locations till 3rd index hence there are all ones, on the other hand let\'s calculate prefix sum till 5th index, and that would be 5 so if there are 6 locations available and sum is 5 then there must be a 0.\n=> The last explanation is all about the solution of this problem. \n=> We can use segment tree or fenwick tree to maintain the prefix sum and then we can find whether there exists all ones till ith index in just O(logn) time.\n=> In the end it is important to note that there is a need of binary search to find the answer.\n\n\n```\n// Fenwick Tree Solution\nclass LUPrefix {\npublic:\n    // `answer` will store the most updated answer at each step\n    int answer;\n    \n    // This is a pointer to the binary indexed tree, we will dynamically allocate an array in constructor\n    int *B_I_Tree;\n\n    // The information about maximum number of input, needed for utilities of  Binary Indexed Tree\n    int n;\n    \n    // Given Constructor\n    LUPrefix(int n) {\n\n        // Initialize `answer` with 0\n        answer = 0;\n\n        // Store the value of `n` so that we can use it later in functions\n        this->n = n;    \n\n        // Dynamically allocate an array of size `n + 1`\n        B_I_Tree = new int[n+1];\n\n        // Fill all the indices with 0\n        memset(B_I_Tree, 0, sizeof(int)*(n+1));\n    }\n    \n    //---------------------------Binary Indexed Tree Utilities------------------------------//\n    void Update(int i, int value) {\n        for(; i<=n ; i+=(i&(-i))){\n            B_I_Tree[i] += value;\n        }\n    }\n    int Sum(int i){\n        int sum = 0;\n        for(; i>0 ; i-=(i&(-i))){\n            sum += B_I_Tree[i];\n        }\n        return sum;\n    }\n    //--------------------------------------------------------------------------------------//\n    \n    void upload(int video) {  \n        // By 0 in binary indexed tree we are indicating that the particular indexed video hasn\'t uploaded yet.\n\n        // So for each upload operation, Update the value at `video` index by 1 \n\n        Update(video, 1);\n    }\n    \n    int longest() {\n\n        // Our answer would always be atleast equal to last answer\n        int low = answer;\n\n        // And at max it can reach to the total number of videos(n)\n        int high = n;\n        \n        // Run a binary search on possible answers\n        while(low<=high){\n            int mid = (low + high)/2;\n        \n            // Check if answer is possible\n            if(Sum(mid) == mid){\n                // If possible then Update the answer\n                answer = mid;\n\n                // And search for some higher answers\n                low = mid + 1;\n            }\n\n            // Otherwise move to lower answers \n            else {\n                high = mid - 1;\n            }            \n        }\n\n        //Return the answer\n        return answer;\n    }\n};\n// @MrTwinkleSharma\n```\n\n\n```\n// Segment Tree Solution\nclass LUPrefix {\npublic:\n    // `answer` will store the most updated answer at each step\n    int answer;\n    \n    // This is a pointer to the segment tree, we will dynamically allocate an array in constructor\n    int *segmentTree;\n\n    // The information about maximum number of input, needed for utilities of Segment Tree\n    int n;\n    \n    // Given Constructor\n    LUPrefix(int n) {\n\n        // Initialize `answer` with 0\n        answer = 0;\n\n        // Store the value of `n` so that we can use it later in functions\n        this->n = n;    \n\n        // Dynamically allocate an array of size `n*4`\n        segmentTree = new int[n*4];\n\n        // Fill all the indices with 0, Because we have no data to separately build the tree\n        memset(segmentTree, 0, sizeof(int)*(n*4));\n    }\n    \n    //---------------------------Segment Tree Utilities------------------------------//\n    void Update(int index, int start, int end, int updateIndex, int value) {\n        // No overlap case\n        if(updateIndex < start || updateIndex > end){\n          return;\n        }\n\n        // Update at leaf node\n        if(start==end){\n          segmentTree[index] = value;\n          return;\n        }\n\n        // Recursively Update both Parts of segment tree\n        int mid = (start + end)/2;\n\n        Update(2*index + 1, start, mid, updateIndex, value);\n        Update(2*index + 2, mid + 1, end, updateIndex, value);\n\n        // Update the segment tree\n        segmentTree[index] = segmentTree[2*index + 1] + segmentTree[2*index + 2];    \n    }\n    int Query(int index, int start, int end, int qstart, int qend){\n        // No overlap\n        if(qend<start || qstart>end){\n          return 0;\n        }\n\n        // Complete Overlap\n        if(qstart<=start && qend>=end){\n          return segmentTree[index];\n        }\n\n        int mid = (start + end)/2;\n        \n        // Recursively find the answer from both subtree\n        return Query(2*index+1, start, mid, qstart, qend) + Query(2*index+2, mid+1, end, qstart, qend);\n    }\n    //--------------------------------------------------------------------------------------//\n    \n    void upload(int video) {  \n        // By 0 in segment tree leaf we are indicating that the particular indexed video hasn\'t uploaded yet.\n\n        // So for each upload operation, Update the value at `video` index by 1 \n\n        // Our segment tree is 0 indexed so use `video - 1` as update index \n        Update(0, 0, n-1, video-1, 1);\n    }\n    \n    int longest() {\n\n        // Our answer would always be atleast equal to last answer\n        int low = answer;\n\n        // And at max it can reach to the total number of videos(n)\n        int high = n;\n        \n        // Run a binary search on possible answers\n        while(low<=high){\n            int mid = (low + high)/2;\n        \n            // Check if answer is possible\n            if(Query(0, 0, n - 1, 0, mid-1) == mid){\n                // If possible then Update the answer\n                answer = mid;\n\n                // And search for some higher answers\n                low = mid + 1;\n            }\n\n            // Otherwise move to lower answers \n            else {\n                high = mid - 1;\n            }            \n        }\n\n        //Return the answer\n        return answer;\n    }\n};\n// @MrTwinkleSharma\n```\n\n\nThe intuition behind disjoint set solution is, \n=> If we create an array of n and mark the uploaded video as 1 and other as 0, then our goal is to find the maximum length of consecutive ones from starting index.\n=> The same thing we can do with disjoint set, we can create disjoint set and for each `upload` operation we can merge the disjoint sets of `video-1` and `video+1` with `video`. But by making sure that video-1 and video+1 have been already uploaded, we can using any kind of hashing for that purpose.\n=> For each Union operation we will always try to make the lower index as parent so that in the end we can get to know the size of 1st disjoint set.\n=> The size of first disjoint set will give the answer. We can maintain the size of disjoint set with the help of rank by size.\n```\n// Disjoint Set solution\nclass LUPrefix {\npublic:\n    // Parent will store the Absolute parent of the Disjoint Set Elements\n    // Rank will store the size of each disjoint set\n    int *parent, *rankBySize;\n    \n    // Total number of `video`, needed later so we are storing it in a global variable\n    int n;\n    \n    // A unordered_map to track the uploaded video\n    unordered_map<int, int> mp;\n    \n    \n    LUPrefix(int n) {\n    \n        this->n = n;\n        \n        // Create the disjoint set array\n        parent = new int[n + 1];\n        rankBySize = new int[n + 1];\n        \n        // Build the disjoint set\n        for(int i = 1;i<=n;i++){\n            parent[i] = i;\n            rankBySize[i] = 1;\n        }\n    }\n    \n    // Find Utility\n    int Find(int node){\n        if(parent[node] == node){\n            return node;\n        }\n        parent[node] = Find(parent[node]);\n        return parent[node];\n    }\n    \n    // Union\n    void Union(int node1, int node2){\n        int p1 = Find(node1);\n        int p2 = Find(node2);\n        \n        if(p1 != p2){\n            \n            // We will always try to merge the parent with higher index into smaller one \n            // Because we want our answer to be concentrated at index `1`\n            if(p1<p2){\n                parent[node2] = node1;\n                rankBySize[p1]+=rankBySize[p2];\n            }\n            else if(p2<p1){\n                parent[node1] = node2;\n                rankBySize[p2]+=rankBySize[p1];\n            }\n        }\n    }\n    \n    void upload(int video) {\n        // Make union of video with video - 1 and video + 1\n        // But make sure that the video - 1 and video + 1 is already uploaded\n        if(video-1>=1 && mp[video-1]==1) Union(video, video-1);\n        if(video+1<=n && mp[video+1]==1) Union(video, video+1);\n        \n        // Upload the video\n        mp[video] = 1;\n    }\n    \n    int longest() {\n        // Return the size of disjoint set having absolute parent `1`.\n        // If 1 video has not been uploaded yet, then still rankBySize will give 1\n        // So we are checking whether `1` video is uploaded or not, as a base case\n        return mp[1] ? rankBySize[1] : 0;\n    }\n};\n//@MrTwinkleSharma\n```\n
['Tree', 'Binary Tree']