Segment Tree | C++ easy explanation
\n#include <bits/stdc++.h>\n#include<algorithm>\n#include<string>\nusing namespace std;\n#define ll int\n// #define int long long\n#define ld long double\n#defi
```\n#include <bits/stdc++.h>\n#include<algorithm>\n#include<string>\nusing namespace std;\n#define ll int\n// #define int long long\n#define ld long double\n#define ff first\n#define ss string \n#define se second\n#define endl "\\n"\n#define ub upper_bound\n#define lb lower_bound\n#define clr(a,x) memset(a,x,sizeof(a))\n#define alt(v) v.begin(),v.end()\n#define ralt(v) v.rbegin(),v.rend()\n#define pb emplace_back\n#define mp make_pair\nconst int N = 2e5+5;\n\n\nll minseg[4*N];\n\n\nvoid update(int nd,int ss,int se,int pos,ll val)\n{\n    if(ss > pos or se < pos)\n        return;\n    if(ss == se and se == pos)\n    {\n        minseg[nd] = val;\n        return;\n    }\n    int mid = (ss+se)/2;\n    update(2*nd,ss,mid,pos,val);\n    update(2*nd+1,mid+1,se,pos,val);\n    minseg[nd] = min(minseg[2*nd],minseg[2*nd+1]);\n}\n\n// we find the smallest index j such that arr[j] <= k and j>=l.\nint query(int nd,int ss,int se,ll k,int l)\n{\n    // the whole segment([ss,se]) not satisfy the condition j >= l and arr[j] <= k\n    if(minseg[nd] > k or se < l)\n        return -2;\n    \n    if(ss == se){\n        if(minseg[nd] <= k)\n            return se;\n        // no element satisfy the given condition.\n        return -1;\n    }\n    \n    int mid = (ss+se)/2;\n    int x = -2;\n    // As we need smallest index so we go first left subtree then right if any element present\n    // in left subtree that satisfy the given condition then we simply return that index otherwise\n    // we go right subtree.\n    x = query(2*nd,ss,mid,k,l);\n    if(x != -2)\n        return x;\n    return query(2*nd+1,mid+1,se,k,l);\n}\n\nclass Solution {\npublic:\n    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) \n    {   \n        // Everytime we start itteration from i%k(curserver) th server as we indicate server from 1 to k(not 0 to k-1) \n        // so we increase the curserver value  by 1 to get actual server.   \n        \n        // If the curserver is 4 then we start to find 1st free server 4 - > 5 -> 6 - > 7 -> 8....-> k-> 1-> 2-> 3 in this way.\n        // if we not get any free server then simply skip that request.\n        \n        // For that we build a circular array of 2*k length and every position indicate (position % k) th server.\n        // i.e position array actually look like as = [1,2,3,4,5...k,1,2,3....k]\n        \n        // In every position we kept the time position%k th server take to finish last request.As initially every server free so \n        // we initialize the array by 0.\n        \n        // i.e array look like arr = [0,0,0,0,0..0] and indexarray = [1,2,3,..k,k+1,k+2,k+3..k+k]\n        \n        //  Everytime we try to find index j that follow the given condition : ->\n        //  i.> j >= curserver(i.e. i%k + 1)\n        //  ii.> arr[j] <= arrival[i] (i.e. j th server take atmost arrival[i] time to finish last request).\n        \n        // Afterthat curserver will be j%k (if the index j = k+5 we indicate that as 5 th server).\n        \n        // we increae the value of cnt_req[curserver] by 1 as 1 more request added to that server.\n        \n        // Afterthat we update the value of arr[curserver] and arr[curserver + k] by arrival[i] + load[i].\n        // i.e. curserver % k th server and (curserver + k)%k server take (arrival[i] + load[i]) time to finish that request.\n        \n        // As initially all element in the array is 0 so we initialize every node in segment tree by 0.\n        for(int i = 1; i <= 8*k; ++i)\n            minseg[i] = 0;\n        \n        vector<int>cnt_req(k+1,0); // initial with 0\n        // cnt_req[i] indicate how many request finish by ith server.\n        \n        for(int i = 0; i < arrival.size();++i)\n        {\n            int curserver = i%k + 1;\n            // query return the free index that is the value of arr[index] <= arrival[i]\n            // and index >= curserver, if no server then it\'s simply return -1. \n            curserver = query(1,1,2*k,arrival[i],curserver);\n            \n            // no free server exist.\n            if(curserver < 0)\n                continue;\n            \n            curserver %= k;\n            if(curserver == 0)\n                curserver = k;\n            \n            cnt_req[curserver]++;\n            update(1,1,2*k,curserver,arrival[i] + load[i]);\n            update(1,1,2*k,curserver + k,arrival[i] + load[i]);\n        }\n        \n        // iterate on cnt_req and find all busiest server.\n        int mxval = *max_element(alt(cnt_req));\n        vector<int>ans;\n        \n        for(int i = 1; i <= k; ++i)\n            if(cnt_req[i] == mxval)\n                ans.pb(i-1); // as question say server indicate 0 to k-1.\n    \n        return ans;\n        \n    }\n};\n\n```\nTime - O(klogk)\nIf any doubt regrading implementation and logic please comment below I am happy to help you.\n
[]