Binary Indexed Trees (BIT or Fenwick tree) + Binary lifting (logN Time Complexity)
ref: https://leetcode-cn.com/circle/article/OeMXPy/\nTwo properties of BIT:\n(1) nodes[i] or sums[i] manages the sum in the range nums[i - i & (-i), i - 1].\ne.
ref: https://leetcode-cn.com/circle/article/OeMXPy/\nTwo properties of BIT:\n(1) nodes[i] or sums[i] manages the sum in the range nums[i - i & (-i), i - 1].\ne.g.\nnodes[4] = nums[0] + nums[1] + nums[2] + nums[3]\nnodes[6] = nums[4] + nums[5]\n(2) parent(i) = i + i&(-i)\n\nAssuming we have added nums[0], ..., nums[7] to our tree. \nThe following figure illustrates how BIT works.\n![image](https://assets.leetcode.com/users/images/edd35b3f-d823-426d-9651-d4f410464cf1_1618455497.7438943.jpeg)\n\nref: https://leetcode.com/problems/finding-mk-average/discuss/1152438/Python3-Fenwick-tree\nref: https://codeforces.com/blog/entry/61364\n[Tutorial] Searching Binary Indexed Tree in O(log(N)) using Binary Lifting\nmake use of binary lifting to achieve O(log(N)) for search_low_boundary\nWhat is binary lifting?\nIn binary lifting, a value is increased (or lifted) by powers of 2,\nstarting with the highest possible power of 2 = 2^\u230Alog(N)\u230B, down to the lowest power, 2^0.\n\nHow binary lifting is used?\nWe are trying to find pos, which is the position of lower bound of v in prefix sums array,\nwhere v is the value we are searching for.\nSo, we initialize pos = 0 and set each bit of pos, from most significant bit to least significant bit.\nWhenever a bit is set to 1, the value of pos increases (or lifts).\nWhile increasing or lifting pos, we make sure that prefix sum till pos should be less than v,\nfor which we maintain the prefix sum and update it whenever we increase or lift pos.\n\n\nTime:\n    addElement: O(logN)\n        N is the parameter of addElement\n    calculateMKAverage: O(logM)\n        M is the max_num = 10^5\n        search_low_boundary takes O(logM)\n        each BinaryIndexTree.query takes O(logM) and there are four queries in total.\nSpace: O(M)\n    M is the max_num = 10^5\n    \nSimilar Questions:\n307. Range Sum Query - Mutable\n308. Range Sum Query 2D - Mutable\n1619. Mean of Array After Removing Some Elements\n1825. Finding MK Average\n\n\n```\n\nimport math\nfrom collections import deque\n\n\nclass BinaryIndexTree:\n    def __init__(self, n: int):\n        self.leng = n + 1\n        """\n        i is the number, nodes[i] = sum(nums[i - i & (-i), i - 1]), \n        nums is the original array\n        e.g.: https://pic.leetcode-cn.com/755dd21358e8cd6ac39c85bdbaa67188dcf67dad7bd8c32d4ad777c1f376ff08-binaryindexedtreeexpandedtreewithinfo.gif\n        """\n        self.nodes = [0] * self.leng\n\n    def query(self, i: int) -> int:\n        """\n        i is a number\n        return the sum of numbers that is less than or equal to,\n        which is equivalent to the sum of logN ranges (\u7B49\u4E8Ei\u4EE3\u8868\u7684logi\u4E2A\u533A\u95F4\u7684\u603B\u548C\u3002)\n        """\n        ans = 0\n        while i:\n            ans += self.nodes[i]\n            i -= i & -i  # remove the lowbit of i\n        return ans\n\n    def update(self, i: int, delta: int) -> None:\n        while i < self.leng:\n            self.nodes[i] += delta\n            # parent(i) = i + i&(-i), i&(-i) is the lowbit of i,\n            # e.g. i = 10, 10 = (1100)2, lowbit(1100_2) = 100_2\n            i += i & -i\n\n\nclass MKAverage:\n\n    def __init__(self, m: int, k: int):\n        """\n        Constraints:\n            3 <= m <= 105\n            1 <= k*2 < m\n            1 <= num <= 105\n            At most 105 calls will be made to addElement and calculateMKAverage.\n        """\n        self.max_num = 10 ** 5\n        self.m = m\n        self.k = k\n        # self.queue_len_limit = m - 2 * k\n        self.queue = deque([])\n        """\n        self.value_tree.query(num) = the sum of the number which <= num\n        self.count_tree.query(num) = the count of the number which <=num\n        """\n        self.value_tree = BinaryIndexTree(self.max_num)\n        self.count_tree = BinaryIndexTree(self.max_num)\n\n        self.remaining_cnt = m - 2 * k\n        self.MKAverage = None  # avoid repetitive computing for MKAverage\n\n    def addElement(self, num: int) -> None:\n        self.value_tree.update(num, num)\n        self.count_tree.update(num, 1)\n        self.queue.append(num)\n        if len(self.queue) > self.m:\n            removed_num = self.queue.popleft()\n            self.value_tree.update(removed_num, -removed_num)\n            self.count_tree.update(removed_num, -1)\n\n        self.MKAverage = None  # avoid recomputing MKAverage if no new number added\n\n    def search_low_boundary(self, count: int) -> int:\n        """\n        search the minimum num that makes self.count_tree.query(num) >= count\n        \u5373self.queue\u4E2D\u5C0F\u4E8E\u7B49\u4E8Enum\u7684\u6570\u81F3\u5C11\u6709count\u4E2A\n        e.g, input 1,\n        self.value_tree.nodes = [0, 1, 3, 3, 10, 5, 11, 7, 36]\n        self.count_tree.nodes = [0, 1, 2, 1, 4, 1, 2, 1, 8]\n        self.max_num = 8\n        i, low_boundary_num, prefix_sum\n        3,   0,     0\n        2,   0,     0\n        1,   2,     2\n        0,   2,     2\n\n        low_boundary_num = 2, low_boundary_num + 1 = 3,\n        so search_low_boundary(3) = 3 means the minimum num that makes self.count_tree.query(num) >= 3\n        """\n        # there are prefix_sum numbers that are less than count\n        low_boundary_num, prefix_sum = 0, 0\n        # self.max_num + 1 \u662Fself.count_tree.sums\u7684\u957F\u5EA6\n        for i in range(int(math.log2(self.max_num + 1)), -1, -1):\n            low_boundary_num2 = low_boundary_num + (1 << i)\n            # print(i, low_boundary_num, prefix_sum, low_boundary_num2)\n\n            if low_boundary_num2 <= self.max_num and prefix_sum + self.count_tree.nodes[low_boundary_num2] < count:\n                prefix_sum += self.count_tree.nodes[low_boundary_num2]\n                low_boundary_num = low_boundary_num2\n\n        # +1 because \'low_boundary_num\' will have position of largest value less than \'count\'\n        return low_boundary_num + 1\n\n    def calculateMKAverage(self) -> int:\n        if len(self.queue) < self.m:\n            return -1\n        if self.MKAverage is not None:\n            return self.MKAverage\n        low_num, high_num = self.search_low_boundary(self.k), self.search_low_boundary(self.m - self.k)\n        num_sum = self.value_tree.query(high_num) - self.value_tree.query(low_num)\n        """\n        https://leetcode.com/problems/finding-mk-average/discuss/1152438/Python3-Fenwick-tree/903394\n        Because probably there are more than k number that is less than or equal to low_num, \n        and there are more than m-k number that is less than or equal to high_num, we have to make some adjustments.\n        \u5373\u6709\u7684\u6570\u591A\u51CF\u4E86, \u6709\u7684\u6570\u5C11\u51CF\u4E86\u3002\u9700\u8981\u91CD\u65B0\u8C03\u6574\n        e.g. m = 6, k = 2, nums = [1,2,2,3,3,4]\n        prefix_sum = [0,1,3,5,6] prefix_sum[i] \u8868\u793A <= i\u7684\u6570\u7684\u4E2A\u6570\n        k1 = k, k2 = m - k = 4\n        -> prefix_sum[lo=2]=3>=k1=2\n        -> prefix_sum[hi=3]=5>=k2=4\n        -> values_tree.query(hi)-values_tree.query(lo) = sum([1,2,2,3,3]) - sum([1,2,2]) = sum([3,3])\n        But the actual solution here is sum([2,3]), we need to remove a 3 and add back a 2.\n        """\n        num_sum += (self.count_tree.query(low_num) - self.k) * low_num\n        num_sum -= (self.count_tree.query(high_num) - (self.m - self.k)) * high_num\n\n        # rounded down to the nearest integer\n        self.MKAverage = num_sum // self.remaining_cnt\n        return self.MKAverage\n```\n
[]