Complexity O(nlogn), Beats 100% solutions
Intuition\n Describe your first thoughts on how to solve this problem. \nThe first idea I come up with is that the sum of AP we can calculate by knowing 3 param
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe first idea I come up with is that the sum of AP we can calculate by knowing 3 parameters: first element ($a$), length ($n$), gap between two elements ($$d=(max - min) / (n - 1) $$).\n\nWe can use this idea in order to use Sum as sort of a Hash function of the arithmetic progression.\n\nBut of course by just calculating the sum will not solve the problem since it\'s easy to provide an example when it doesn\'t work f.e. [0, 3, 3, 6] (we the sum is 12 which complitly matches with correct AP [0, 2, 4, 6]).\n\nAnd what we can do then?\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nThe idea is to find a second / third hash function in order to double verifty the solution when the first hashing is not working.\n\nAnd here is a second hash function: let\'s take a sum of squares!\n\nWe can easily calculate the formula of sum of elements of AP by taking only 3 parameters as well:\n\n\n\n$$\\sum_{k=1}^n(a + d * (k - 1))^2 = \\sum_{k=1}^n(a^2 + 2d(k-1)+d^2(k-1)^2)=na+2d\\sum_{k=1}^n(k-1) +d^2 \\sum_{k=1}^n(k-1)^2 = na + 2d*n(n-1)/2+d^2*n(n-1)(2n-1)/6$$\n\nThe same way we could get a third hash function by unwrapping the cubic equation. \n\nSo, what we do next we this knowlege.\n\nWe need to have some data structure which can count the sum of elements on the segment, minimum and maximum on segment.\n\nIn my solution I used Fenwik tree for finding min/max for qieries, but we can use the segment tree as well (the complexity will not change).\n\nPreffix sums can be used for calculating the sum (and sum of squares) of segment.\n\nThe solution is to first precalculate min/max, sum and sum of squares on segments from queries, and then just by calculating them by formula we can compare the sums to calculate the answer.\n\nP.s. I wanted to make it $$O(n)$$ but I can\'t do min/max queries faster than $$O(n*log(n))$$. Apretiate any help to make it $$O(n)$$\n\n# Complexity\n- Time complexity: $$O(m*log(n))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n[Accepted code](https://leetcode.com/problems/arithmetic-subarrays/submissions/1105436452)\n\n# Code\n```\nconst int inf = (int) 1e9;\n\nclass Solution {\npublic:\n\n    \n    struct Fenwik {\n        vector<pair<int,int>> t;\n        int n_;\n        \n\n        Fenwik(int n) : t(n + 10, {inf, -inf}), n_(n) {};\n\n        void Add(int pos, int a) {\n            for (; pos < n_; pos |= pos + 1) {\n                t[pos] = {min(t[pos].first, a), max(t[pos].second, a)};\n            }\n        }\n\n        pair<int,int> Get(int pos) {\n            int mi= inf, ma=-inf;\n            for (; pos >= 0; pos &= pos + 1, pos--) {\n                mi = min(mi, t[pos].first);\n                ma = max(ma, t[pos].second);\n            }\n            return {mi, ma};\n        }\n\n    };\n\n    long long sum(int n, int a, int d) {\n        return 1ll * (2ll * a + 1ll * (n - 1) * d) * n / 2;\n    }\n\n    long long sum2(int n, int a, int d) {\n        return 1ll * d * d * n * (n - 1) * (2 * n - 1) / 6 + 1ll * n * a * a + 1ll * a * d * n * (n - 1) ;   \n    }\n\n    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {\n        Fenwik f(nums.size());\n        vector<vector<int>> queries(nums.size());\n        for (int i = 0; i < l.size(); i ++) {\n            queries[ l[i] ].push_back(i);\n        }\n        vector<bool> ans(l.size());\n        vector<long long> psum(nums.size()), psum2(nums.size());\n        for (int i = 0; i < nums.size(); i ++) {\n            psum[i] = nums[i];\n            psum2[i] = nums[i] * nums[i];\n            if (i) {\n                psum[i] += psum[i - 1];\n                psum2[i] += psum2[i - 1];\n            }\n        }\n\n        vector<pair<int, int>> qres(l.size());\n        for (int i = nums.size() - 1; i >= 0; i --) {\n            f.Add(i, nums[i]);\n            for (int v : queries[i]) {\n                qres[v] = f.Get(r[v]);\n            }\n        }\n        \n        for (int i = 0; i < l.size(); i ++) {\n            long long s = psum[r[i]] - (l[i] ? psum[l[i] - 1] : 0);\n            long long s2 = psum2[r[i]] - (l[i] ? psum2[l[i] - 1] : 0);\n            auto[mi, ma] = qres[i];\n            int dist = ma - mi;\n            int len = r[i] - l[i] + 1;\n            if (dist == 0) {\n                ans[i] = true; \n                continue;\n            }\n            if (dist % (len - 1) != 0) {\n                ans[i] = false;\n                continue;\n            }\n            int gap = dist / (len - 1);\n            ans[i] = (sum(len, mi, gap) == s && sum2(len, mi, gap) == s2);\n        }\n        return ans;\n    }\n};\n```\n
['Segment Tree', 'Hash Function', 'Prefix Sum', 'C++']