Segment Tree & prefix sum Solution || Very slow but unique || C++
As most of the solutions posted here is highly dependent on prefix array sum and other techniques, I thought that solving using segment tree is a pretty unique 
As most of the solutions posted here is highly dependent on prefix array sum and other techniques, I thought that solving using segment tree is a pretty unique idea.\n\nThis is a materialized idea of the HINTS 1 & 2 provided there.\n\n```\nclass segment_tree {\nvector<int> seg;\nint size;\npublic:\nsegment_tree(vector<int>& a) {\n    size = a.size();\n    seg.resize(2*size+5);\n    for(int i = 0; i < a.size(); i++) \n        update(i, a[i]);\n}\nvoid update(int i, int val) {\n    i += size;\n    seg[i] += val;\n    for(i /= 2; i >= 1; i /= 2) \n        seg[i] = seg[i*2] + seg[i*2+1];\n}\nint query(int l, int r) {\n    l += size, r += size;\n    int sm = 0;\n    while(l <= r) {\n        if(l % 2 == 1) sm += seg[l++];\n        if(r % 2 == 0) sm += seg[r--];\n        l /= 2, r /= 2;\n    }\n    return sm;\n}\n};\n\nint sumOfFlooredPairs(vector<int>& a) {\n    int mod = (int)1e9+7;\n    int mx = 0;\n    unordered_map<int, long long> mp;\n\n    for(int i = 0; i < a.size(); i++) mx = max(mx, a[i]);\n    vector<int> pref(mx+1);\n    for(int i = 0; i < a.size(); i++) pref[a[i]]++, mp[a[i]]++;\n    segment_tree seg(pref);\n    \n\n    long long ans = 0;\n    for(auto x : mp) {\n        int occ = 0;\n        int j;\n        for(j = x.first; j <= pref.size(); j += x.first) {\n            ans += (seg.query(j - x.first, j-1) * occ) * x.second;\n            ans %= mod;\n            occ++;\n        }\n        if(j > pref.size()) ans += ((seg.query(j - x.first, pref.size()-1) * occ) * x.second), ans %= mod;\n    }\n    return ans % mod;\n}\n```\n
['Tree', 'C', 'Prefix Sum']