prefix sum on ranges
Intuitionevery valid segment will either start on li and go upto k forward or end at ri and go k backward. We can use prefix sum to calculate the sum between th
# Intuition
every valid segment will either start on li and go upto k forward or end at ri and go k backward. We can use prefix sum to calculate the sum between these ranges and then just bruteforce.

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
O(nlogn)

- Space complexity:
O(n)

# Code
```cpp []
#define ll long long
class Solution {
public:
    map<ll, ll> prefix;
    map<ll, pair<ll, ll>> mp;

    ll getPrefixSum(ll coord){
        if(coord < 1)
            return 0;

        ll ans = 0;
        auto it1 = prefix.upper_bound(coord);
        if(it1 != prefix.begin())
            it1--, ans += it1->second;

        auto it2 = mp.upper_bound(coord);
        if(it2 != mp.begin()){
            it2--;
            if(coord < it2->second.first)
                ans += (coord - it2->first + 1) * it2->second.second;
        }

        return ans;
    }

    ll getLtoR(ll l, ll r){
        return getPrefixSum(r) - getPrefixSum(l - 1);
    }

    ll maximumCoins(vector<vector<int>>& coins, int k) {
        sort(coins.begin(), coins.end());

        ll sum = 0;
        for(auto it : coins){
            sum += 1ll * it[2] * (it[1] - it[0] + 1);
            prefix[it[1]] = sum;
            mp[it[0]] = {it[1], it[2]};
        }

        ll ans = 0;
        for(auto it : coins){
            // forward
            ans = max(ans, getLtoR(it[0], it[0] + k - 1));
            cout << getLtoR(it[0], it[0] + k - 1) << "\n";

            // backward
            if(it[1] >= k)
                ans = max(ans, getLtoR(it[1] - k + 1, it[1]));
        }

        return ans;
    }
};
```
['C++']