C++ | Prefix sum | Adjust counts
Intuition\nCount all pair of points with shortest paths.\nFor i 0-1-2-...-i....-n-1, \ni- i-1 has len = 1\ni -> i-2 has len 2 \ni->0 len i\netc. ie, we get lens
# Intuition\nCount all pair of points with shortest paths.\nFor i 0-1-2-...-i....-n-1, \ni- i-1 has len = 1\ni -> i-2 has len 2 \ni->0 len i\netc. ie, we get lens 0,1,2..i \nsimilary for i->n-1, we get 0,1,2,,n-1-i.\n\nNow adjust counts of (i,p) such that it is shorter to take the x-y edge\nand then visit p, than directly going to p.\n\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n# Code \n```cpp\nclass Solution {\npublic:\n    vector<long long> countOfPairs(int n, int x, int y) {\n        x--;\n        y--;\n\n        if (x > y){\n            swap(x, y);\n        }\n\n        vector<long long> ans(n+1);\n\n        auto update = [&](int i,int j,int val){\n            ans[i] += val;\n            ans[j+1] -= val;\n            return;\n        };\n\n        \n        for(int i = 0 ;i<n;i++){\n            update(0,i,1);\n            update(0,n-1-i,1);\n            if(x==y || x== y-1){\n                continue;\n            }\n            /*\n                for all points p which are better of taking the path\n                i->x->y->p instead of i->x->p\n\n                p-i >= x-i+i+y-p\n\n                Note: It is enough to solve with for p-i > x-i+i+y-p,\n                but out equation is on the assumption that p <= y (y-p) distance.\n                This might not be true for >, but is true for >= (Try some examples).\n\n\n            */\n            if(i<=x){\n                int p = ceil((x+y+1)/2.0);\n                // Remove paths i- > p..->n-1 (remove edged p-1->p,p->p+1 ..)\n                update(p-i,n-1-i,-1);\n                // Add paths i->x->y->p\n                update(x-i+1,x-i+1+y-p,1);\n                // Add paths i->x->y->n-1;\n                // x-i + 2 because i->x->y is counted in earliear step/\n                update(x-i+2,x-i+1+n-1-y,1);\n            } else if(i>=y){\n                /*\n                    i-p>=i-y+1+p-x\n                */\n                int p = floor((x+y-1)/2.0);\n                update(i-p,i,-1);\n                update(i-y+1,i-y+1+p-x,1);\n                update(i-y+2,i-y+1+x,1);\n            } else {\n                // if p is equidistant from x and p, skip\n                if(abs(i-x) < abs(i-y)){\n                    /*\n                        p-i >= i-x+1+y-p\n                    */\n                    int p = ceil( (2*i-x+y+1)/2.0 );\n                    update(p-i,n-1-i,-1);\n                    update(i-x+1,i-x+1+y-p,1);\n                    update(i-x+2,i-x+1+n-1-y,1);\n                } else if (abs(i-y) < abs(i-x)) {\n                    /*\n                        i-p >= y-i+1+p-x\n                    */\n                    int p = floor((2*i+x-y-1)/2.0);\n                    update(i-p,i,-1);\n                    update(y-i+1,y-i+1+p-x,1);\n                    update(y-i+2,y-i+1+x,1);\n                }\n            }\n        }\n        for(int i = 1;i<=n;i++){\n            ans[i] += ans[i-1];\n        }\n        return vector<long long>(ans.begin() +1,ans.end());\n\n    }\n};\n```
['C++']