Range Sum Query || Prefix Sum || O(N) || Beats 100% || Cpp
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> countOfPairs(int n, int x, int y) {\n        vector<int> dist(n);\n        vector<int> pref(n+1);\n\n        if(x > y)swap(x,y);\n\n        if(x == y || x+1 == y){\n            for(int i = 1 ; i <= n ; i++){\n                pref[1]++;\n                pref[n - i + 1]--;\n            }\n        }\n        else{\n            int m = y - (y - x)/2;\n            for(int i = m ; i <= n ; i++){\n                pref[1]++;\n                pref[n - i + 1]--;\n            }\n\n            for(int i = 1 ; i < x ; i++){\n                pref[1]++;       pref[m-i+1]--;\n                pref[x-i+1]++;   pref[(x-i+1)+y-m]--;\n                pref[x-i+1+1]++; pref[(x-i+1)+n-y+1]--;\n            }\n\n            int p = m;\n            for(int i = x ; i < m ; i++){\n                pref[1]++;       pref[p-i+1]--;\n                pref[i-x+1]++;   pref[(i-x+1)+y-p]--;\n                pref[i-x+1+1]++; pref[(i-x+1)+n-y+1]--;\n                p++;\n            }\n        }\n        for(int i = 1 ; i <= n ; i++){\n            pref[i] += pref[i-1];\n            dist[i-1] = pref[i] * 2;\n        }\n        return dist;\n    }\n};\n```
['Prefix Sum', 'C++']