Optimized solution O(MlogN) — SegmentTree + Cumsum + Cumsum of squares
Approach\n Describe your first thoughts on how to solve this problem. \n1. In the original solution, the author offered to find minimal and maximal elements jus
# Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. In the original solution, the author offered to find minimal and maximal elements just passing through the array for $$O(N)$$. We can optimize the complexity to $$O(logN)$$ using two segment trees.\n2. To check if the subarray is the arithmetic progression we can calculate the sum of elements and sum of squares of elements and compare them to expected ones.\nTo find the sum of elements and sum of squares of elements for $$O(1)$$ we have to use precalculated cumulative sum.\n \n## Expected sum of elements \nSum of the arithmetic progression formula can be easily googled:\n\n$$S=\\frac{(2a_0+d(n-1)) \\cdot n}{2}$$\n\nAnd we can calculate the sum of the arithmetic progression suqares:\n$$S^2=\\sum_{i=0}^{n-1}(a_0+di)^2 = \\sum_{i=0}^{n-1}(a_0^2+2 a_0di+d^2i^2)=a_0^2 \\cdot n+2a_0d\\sum_{i=0}^{n-1}i+d^2\\sum_{i=0}^{n-1}i^2=a_0^2 \\cdot n+2a_0d \\cdot \\frac{n(n-1)}2+d^2 \\cdot \\frac{n(n-1)(2n-1)}6$$\n\nWhere $$a_0$$ is the first element of the progression and $$d$$ is the common difference of successive members.\n# Complexity\n- Time complexity: $$O(N+MlogN)$$.\n$$O(N)$$ is used for the precalculations of segment trees and cumulative sums.\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nimport math\nimport operator\n\nfrom itertools import accumulate\n\n\nclass SegmentTree:\n    def __init__(self, length, neutral_element=0, operator=operator.add):\n        self.operator = operator\n        self.neutral_element = neutral_element\n        self._length = length\n        self._inner_size = 1 << math.ceil(math.log2(length))\n        self._array = [neutral_element] * (self._inner_size * 2 - 1)\n\n    def __len__(self):\n        return self._length\n\n    @staticmethod\n    def from_array(array, neutral_element=0, operator=operator.add):\n        result = SegmentTree(len(array), neutral_element, operator)\n        result.build(array)\n        return result\n\n    def build(self, array):\n        if len(array) != self._length:\n            raise ValueError(\'There are different lengths of arrays\')\n        self._build(array, 0, 0, self._inner_size)\n\n    def _build(self, array, st_index, st_left, st_right):\n        if st_right - st_left == 1:\n            if st_left < len(array):\n                self._array[st_index] = array[st_left]\n            return\n\n        st_mid = (st_left + st_right) // 2\n        self._build(array, 2 * st_index + 1, st_left, st_mid)\n        self._build(array, 2 * st_index + 2, st_mid, st_right)\n        self._array[st_index] = self.operator(\n            self._array[2 * st_index + 1],\n            self._array[2 * st_index + 2]\n        )\n\n    def _update_index(self, index, right_bound=False):\n        if not isinstance(index, int):\n            raise TypeError(f\'Expected int, got: {type(index)}\')\n        if not (-self._length - right_bound <= index < self._length + right_bound):\n            raise IndexError(f\'index should be between 0 and {self._length + right_bound}\')\n        if index < 0:\n            index += self._length\n        return index\n\n    def __getitem__(self, index):\n        if not isinstance(index, slice):\n            index = self._update_index(index)\n            return self._array[index - self._inner_size]\n        if index.step is not None:\n            raise ValueError(f\'Steps are not supported\')\n        start_index = self._update_index(index.start)\n        end_index = self._update_index(index.stop, True)\n        return self._get(start_index, end_index, 0, 0, self._inner_size)\n\n    def _get(self, left, right, st_index, st_left, st_right):\n        if st_left >= right or left >= st_right:\n            return self.neutral_element\n\n        if left <= st_left and st_right <= right:\n            return self._array[st_index]\n\n        st_mid = (st_left + st_right) // 2\n\n        lvalue = self._get(left, right, 2 * st_index + 1, st_left, st_mid)\n        rvalue = self._get(left, right, 2 * st_index + 2, st_mid, st_right)\n\n        return self.operator(lvalue, rvalue)\n\n    def __setitem__(self, index, value):\n        index = self._update_index(index)\n        self._set(index, value, 0, 0, self._inner_size)\n\n    def _set(self, index, value, st_index, st_left, st_right):\n        if st_right - st_left == 1:\n            self._array[st_index] = value\n            return\n\n        st_mid = (st_left + st_right) // 2\n        if index < st_mid:\n            self._set(index, value, 2 * st_index + 1, st_left, st_mid)\n        else:\n            self._set(index, value, 2 * st_index + 2, st_mid, st_right)\n\n        self._array[st_index] = self.operator(\n            self._array[2 * st_index + 1],\n            self._array[2 * st_index + 2]\n        )\n\n    def __iter__(self):\n        for i in range(self._length):\n            yield self._array[i - self._inner_size]\n\n\nclass Solution:\n    def checkArithmeticSubarrays(self, nums: list[int], l: list[int], r: list[int]) -> list[bool]:\n        cumsum = list(accumulate(nums))\n        squared_cumsum = list(accumulate(value ** 2 for value in nums))\n\n        min_segment_tree = SegmentTree.from_array(nums, neutral_element=math.inf, operator=min)\n        max_segment_tree = SegmentTree.from_array(nums, neutral_element=-math.inf, operator=max)\n        \n        m = len(l)\n        result = [False] * m\n        for i, left, right in zip(range(m), l, r):\n            length = right - left + 1\n            if length <= 2:\n                result[i] = True\n                continue\n\n            min_value = min_segment_tree[left: right + 1]\n            max_value = max_segment_tree[left: right + 1]\n\n            diff, mod = divmod(max_value - min_value, length - 1)\n            if mod != 0:\n                continue\n\n            expected_sum = (min_value + max_value) * length // 2\n            real_sum = cumsum[right] - (cumsum[left - 1] if left else 0)\n\n            if expected_sum != real_sum:\n                continue\n\n            expected_squared_sum = min_value ** 2 * length \\\n                              + diff * min_value * length * (length - 1) \\\n                              + diff ** 2 * (length - 1) * length * (2 * length - 1) // 6\n            real_squared_sum = squared_cumsum[right] - (squared_cumsum[left - 1] if left else 0)\n\n            if expected_squared_sum != real_squared_sum:\n                continue\n\n            result[i] = True\n\n        return result\n\n```
['Math', 'Segment Tree', 'Prefix Sum', 'Python3']