Fenwick Tree Solution || Explained
Complexity\n- Time complexity: O(n*log(n)) \n\n- Space complexity: O(n) \n\n# Code\n\n#define mod 1000000007\nclass FenwickTree\n{\n    vector<int> BIT;\n    pu
# Complexity\n- Time complexity: $$O(n*log(n))$$ \n\n- Space complexity: $$O(n)$$ \n\n# Code\n```\n#define mod 1000000007\nclass FenwickTree\n{\n    vector<int> BIT;\n    public:\n    FenwickTree(int n) {\n        BIT.resize(n+1);\n    }\n\n    void update(int i, int delta)\n    {\n        for(; i<int(BIT.size()); i += (i&-i)) {\n            BIT[i] += delta;\n        }\n    }\n\n    long long query(int i)\n    {\n        long long sum = 0;\n        for(; i>0; i -= (i&-i)) {\n            sum += BIT[i];\n        }\n     return sum;\n    }\n};\n\nclass Solution {\npublic:\n    int sumOfFlooredPairs(vector<int>& nums) {\n        FenwickTree ft(100001);\n        long long maxi = 0, ans = 0;\n        unordered_map<int,int> mpp;\n\n        for(auto it : nums) {\n            mpp[it]++;\n            maxi = max(maxi,1LL*it);\n            ft.update(it,1); //update number in Fenwick Tree\n        }\n\n        for(auto it : mpp) { //for each unique number\n            int x = it.first;\n            for(long long k = 1; k<=maxi/x; k++) {\n                //all numbers \'num\' in range [l,r] will give floor(x/num) = k\n                long long r = (k+1)*x-1, l = k*x-1; \n                ans = (ans + mpp[x] * k * (ft.query(min(maxi,r)) - ft.query(l))) % mod;            \n            } //since every occurence of x will give same ans, we multiply by mpp[x]\n        }\n     return ans;\n    }\n};\n```
['Binary Indexed Tree', 'C++']