[Python] Fenwick Tree O(n log(k))
Goal:\n\nThe objective here is to iterate over the list of jobs (arrival times and loads) and assign each job to a server. \nKeep track of how many jobs each se
**Goal:**\n\nThe objective here is to iterate over the list of jobs (arrival times and loads) and assign each job to a server. \nKeep track of how many jobs each server handled and return a list of the most productive servers.  \n\n**Approach:**\n\nAt the beginning all the servers are free.\nAssign the first job to server 0, the second job to server 1, ..., the k<sup>th</sup> to server k-1.  No problems.\n\nAfter the first k jobs have been assigned, a server must start it\'s second job.\nTo find out which servers are done with their first job and ready to accept a second job,\nwe could iterate over a list of servers and see which servers have an end time less than \nor equal to the current time. But this would be very time consuming.  \n\nInstead store the busy servers in a min-heap where each busy server is a tuple (end_time, server_id).  \nWhere end_time is the time that the server will finish its current job and server_id is the index of the server.  \nAll busy servers with an end_time earlier than the current time (arrival[i]) are now free and can be popped off the server heap.  \n\nAssign the current job to the first free server to the right of the current index.  \nWrap around to the start of the server list if necessary.  \nKeep count of how many jobs each server receives in a hash map.\nOnce all jobs have been assigned to servers - or dropped - return a list of the most productive servers.  \n\n**The Challenge:**\n\nThis problem is more than deserving of it\'s hard rating.  \nWhat makes this problem difficult is finding the first free server in **less than** linear time.  \n\nThe first free server can be found with a linear search (as shown in the Simple Solution).\nHowever, this will result in an overall time complexity of O(n<sup>2</sup>) which will TLE.\n\nIn the aptly named Fenwick Tree Solution, a Fenwick Tree is used to speed up the process of finding the first free server.\nFenwick trees serve the same purpose as a presum array in that they provide fast range sum queries.\nThe difference is that they take a little longer to query **but** they are much faster to update.  \n\n| |Create| Range Sum Query|Update|\n|---|---|---|---|\n|Fenwick Tree| O(n)| O(log(n)) | O(log(n)) |\n|Presum Array| O(n) | O(1) | O(n) |\n\nTo use a Fenwick tree to find the first free server, use a binary array servers where server[i] = 1 \nmeans the i<sup>th</sup> sever is busy and server[i] = 0 means the i<sup>th</sup> server is free.  \n\nIf a free server exists in the range [i, j] then the range sum query of range [i, j] will be less than the length of the range.  \nThen binary search for the left-most range of length 1 that has a sum of 0.  \n\n\n**Observations:**\n\nIf there are more servers than there are jobs, then the first n servers will all get 1 job.\nThe solution reduces to range(n) where n is the number of jobs. \n\nIf there is only one free server, then that server **must** receive the current job.  \nKeep track of which servers are not busy in a set.  \nWhen the length of the set is 1, we can assign the current job in O(log(n)) time as opposed to O(log(n)<sup>2</sup>) time.  \n\n<details>\n\n<b><summary>Simple Solution: (click to show)</summary></b>\n\n```python\n#Runtime: TLE\nclass Solution:\n    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n        \n        requests_handled = collections.defaultdict(int)\n        servers = [] # server heap (end_time, server_id)\n        free_servers = set(range(k))\n        \n        for i, (t, c) in enumerate(zip(arrival, load)):\n            \n            while servers and servers[0][0] <= t:\n                free_servers.add(heapq.heappop(servers)[1])\n            \n            if free_servers:\n                \n                # find first free server\n                target_server = i % k\n                while target_server not in free_servers:\n                    target_server = (target_server + 1) % k\n                \n                # mark the server as busy\n                free_servers.remove(target_server)\n                \n                # add the server to the server heap\n                heapq.heappush(servers, (t + c, target_server))\n                requests_handled[target_server] += 1\n        \n        maxi = max(requests_handled.values())\n        return [server for server in requests_handled if requests_handled[server] == maxi]\n```\n\n</details>\n\n\n<details>\n\n<b><summary>Fenwick Tree Solution: (click to show)</summary></b>\n\n```python\n# Runtime: 4264 ms\nclass Fenwick(object):\n    def __init__(self, arr):\n        self.arr = [0] + arr\n        self.fen = self.arr[:]\n        self.construct()\n    \n    def construct(self):\n        for i in range(len(self.fen)):\n            j = i + self.lsb(i)\n            if j < len(self.fen):\n                self.fen[j] += self.fen[i]\n            \n    def lsb(self, n):\n        \'\'\'return the least significant bit of n\'\'\'\n        return -n&n\n    \n    def presum(self, i):\n        \'\'\'return sum of array from 0:i\'\'\'\n        res = 0\n        while i:\n            res += self.fen[i]\n            i -= self.lsb(i)\n        return res\n    \n    def range_sum(self, i, j):\n        \'\'\'return sum of array from i: j inclusive\'\'\'\n        i, j = i+1, j+1\n        return self.presum(j) - self.presum(i-1)\n    \n    def update(self, i, val):\n        \'\'\'change value at arr[i] to val ; i.e. arr[i] = 1 if server busy and arr[i] = 0 if free\'\'\'\n        i += 1\n        diff = val - self.arr[i]\n        self.arr[i] = val\n        while i < len(self.fen):\n            self.fen[i] += diff\n            i += self.lsb(i)\n    \n    def free_server_in_range(self, i, j):\n        \'\'\'returns True if there is a free server in the range [i,j] inclusive\'\'\'\n        return self.range_sum(i-1, j-1) < (j - i + 1)\n    \n    def binary_search(self, low, high):\n        \'\'\'Finds the left-most server that is free in the range low, high inclusive\'\'\'\n        first_free = float(\'inf\')\n        if self.free_server_in_range(low, high):\n            while low <= high:\n                j = (low + high) // 2\n                if self.free_server_in_range(low, j):\n                    first_free = min(j, first_free)\n                    high = j - 1\n                else:\n                    low = j + 1\n        return first_free\n    \n    def find_first_free_server(self, i):\n        \'\'\'Returns the index of the first free server to the right of server i (wrapping around to server 0 if needed)\'\'\'\n        first_free = self.binary_search(i, len(self.arr) - 1)\n        return (first_free - 1) if (first_free != float(\'inf\')) else (self.binary_search(1, i-1) - 1)\n\n    \nclass Solution:\n    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n        \n        if k >= len(arrival):          # If we have more servers than jobs then\n            return range(len(arrival)) # the first n servers will all receive 1 job\n        \n        end = [a + c for a,c in zip(arrival, load)]                                  # end[i] is the time at which the (i)th job will finished\n        requests_handled = collections.defaultdict(lambda: 1)                        # All servers get one job to start with\n        t_naught = arrival[k]                                                        # Arrival time of the (k)th job\n        free_servers = Fenwick([int(end[i] > t_naught) for i in range(k)])           # All servers that finish their job before t_naught are free\n        not_in_use = set(i for i in range(k) if end[i] <= t_naught)                  # Set of servers that are free\n        servers = [(arrival[i] + load[i], i) for i in range(k) if end[i] > t_naught] # active server heap (end_time, server_id)\n        heapq.heapify(servers)\n        \n        for i in range(k, len(arrival)):\n            t = arrival[i]\n            e = end[i]\n            i = i % k\n            \n            while servers and servers[0][0] <= t:  # Remove all servers that have completed their job from the server heap\n                s = heapq.heappop(servers)[1]\n                free_servers.update(s, 0)          # 0 means the server is now free\n                not_in_use.add(s)\n            \n            if len(servers) < k - 1:\n                target_server = free_servers.find_first_free_server(i+1) if free_servers.arr[i+1] else i\n                not_in_use.remove(target_server)             # mark server as not free\n                free_servers.update(target_server, 1)        # 1 means the server is now busy\n                heapq.heappush(servers, (e, target_server))  # add server to server heap\n                requests_handled[target_server] += 1         # Record that server handled 1 request\n            elif len(servers) == k - 1:\n                target_server = not_in_use.pop()             # There is only one server available to use\n                free_servers.update(target_server, 1)        # mark server as busy\n                heapq.heappush(servers, (e, target_server))  # add server to server heap\n                requests_handled[target_server] += 1         # Record that server handled 1 request\n                \n        maxi = max(requests_handled.values())\n        return (server for server in requests_handled if requests_handled[server] == maxi)\n```\n\n</details>
['Tree', 'Heap (Priority Queue)', 'Python', 'Python3']